Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
Comparative Study
. 2003 Jan;13(1):97-102.
doi: 10.1101/gr.789803.

AVID: A global alignment program

Nick Bray  1 , Inna Dubchak, Lior Pachter
Affiliations
Comparative Study

AVID: A global alignment program

Nick Bray et al. Genome Res. 2003 Jan.

Abstract

In this paper we describe a new global alignment method called AVID. The method is designed to be fast, memory efficient, and practical for sequence alignments of large genomic regions up to megabases long. We present numerous applications of the method, ranging from the comparison of assemblies to alignment of large syntenic genomic regions and whole genome human/mouse alignments. We have also performed a quantitative comparison of AVID with other popular alignment tools. To this end, we have established a format for the representation of alignments and methods for their comparison. These formats and methods should be useful for future studies. The tools we have developed for the alignment comparisons, as well as the AVID program, are publicly available. See Web Site References section for AVID Web address and Web addresses for other programs discussed in this paper.

PubMed Disclaimer

Figures

Figure 1.
Figure 1.
The AVID algorithm structure.
Figure 2.
Figure 2.
Finding maximal matches using a suffix tree: The suffixes of the word at the root are represented by the characters along the paths from the root to the leaves. Branchings in the tree correspond to locations where different suffixes shared the same prefix, and therefore are matches. Every internal node in the tree is therefore a match (with the matching sequence corresponding to the path characters along the path from the root). Maximal matches can be efficiently detected by considering some additional criteria.
Figure 3.
Figure 3.
Selecting anchors from the set of matches. Every maximal match is shown in blue. A set of good anchors is shown in red.
Figure 4.
Figure 4.
Cat versus mouse: A VISTA picture showing an AVID alignment of the 5′ region of the MET gene in cat and mouse. The top panel shows the alignment of the two finished sequences with the X-axis showing coordinates in the mouse, and the Y-axis showing the %identity in a 100-bp window. The bottom panel shows the results of a draft placement simulation: the cat sequence has been sliced at locations corresponding to the vertical black lines. The resulting contigs were permuted (order and orientation changed randomly) and realigned to the mouse.
See this image and copyright information in PMC

References

    1. Altschul S.F., Gish, W., Miller, W., Myers, E.W., and Lipman, D.J. 1990. Basic local alignment search tool. J. Mol. Biol. 215: 403-410. - PubMed
    1. Batzoglou S., Pachter, L., Mesirov, J.P., Berger, B., and Lander, E.S. 2000. Human and mouse gene structure: Comparative analysis and application to exon prediction. Genome Res. 10: 950-958. - PMC - PubMed
    1. Benos P.V., Gatt, M.K., Murphy, L., Harris, D., Barrell, B., Ferraz, C., Vidal, S., Brun, C., Demaille, J., Cadieu, E., et al. 2001. From first base: The sequence of the tip of the X chromosome of Drosophila melanogaster, a comparison of two sequencing strategies. Genome Res. 11: 710-730. - PMC - PubMed
    1. Brudno M. and Morgenstern, B., 2002. Fast and sensitive alignment of large genomic sequences. In Proceedings of the First IEEE Computer Society Conference on Bioinformatics. IEEE Computer Society Press. - PubMed
    1. Burset M. and Guigo, R. 1996. Evaluation of gene structure prediction programs. Genomics 34: 353-357. - PubMed

Publication types

Substances

LinkOut - more resources