MAVID: Constrained Ancestral Alignment of Multiple Sequences

Overview

Journal Genome Res

Specialty Genetics

Date 2004 Apr 3

PMID 15060012

Citations 119

Authors

Nicolas Bray

Lior Pachter

Affiliations

Soon will be listed here.

Abstract

We describe a new global multiple-alignment program capable of aligning a large number of genomic regions. Our progressive-alignment approach incorporates the following ideas: maximum-likelihood inference of ancestral sequences, automatic guide-tree construction, protein-based anchoring of ab-initio gene predictions, and constraints derived from a global homology map of the sequences. We have implemented these ideas in the MAVID program, which is able to accurately align multiple genomic regions up to megabases long. MAVID is able to effectively align divergent sequences, as well as incomplete unfinished sequences. We demonstrate the capabilities of the program on the benchmark CFTR region, which consists of 1.8 Mb of human sequence and 20 orthologous regions in marsupials, birds, fish, and mammals. Finally, we describe two large MAVID alignments, an alignment of all the available HIV genomes and a multiple alignment of the entire human, mouse, and rat genomes.

Citing Articles

Multiple genome alignment in the telomere-to-telomere assembly era.

Kille B, Balaji A, Sedlazeck F, Nute M, Treangen T Genome Biol. 2022; 23(1):182.

PMID: 36038949 PMC: 9421119. DOI: 10.1186/s13059-022-02735-6.

Comparative analyses of the Hymenoscyphus fraxineus and Hymenoscyphus albidus genomes reveals potentially adaptive differences in secondary metabolite and transposable element repertoires.

Elfstrand M, Chen J, Cleary M, Halecker S, Ihrmark K, Karlsson M BMC Genomics. 2021; 22(1):503.

PMID: 34217229 PMC: 8254937. DOI: 10.1186/s12864-021-07837-2.

Multiple Alignment of Promoter Sequences from the L. Genome.

Korotkov E, Suvorova Y, Kostenko D, Korotkova M Genes (Basel). 2021; 12(2).

PMID: 33494278 PMC: 7909805. DOI: 10.3390/genes12020135.

Progressive Cactus is a multiple-genome aligner for the thousand-genome era.

Armstrong J, Hickey G, Diekhans M, Fiddes I, Novak A, Deran A Nature. 2020; 587(7833):246-251.

PMID: 33177663 PMC: 7673649. DOI: 10.1038/s41586-020-2871-y.

Draft genomes of two outcrossing wild rice, and , reveal genomic features associated with mating-system evolution.

Li W, Zhang Q, Zhu T, Tong Y, Li K, Shi C Plant Direct. 2020; 4(6):e00232.

PMID: 32537559 PMC: 7287411. DOI: 10.1002/pld3.232.

References

Holmes I . Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics. 2003; 19 Suppl 1:i147-57. DOI: 10.1093/bioinformatics/btg1019. View

Felsenstein J . Evolutionary trees from DNA sequences: a maximum likelihood approach. J Mol Evol. 1981; 17(6):368-76. DOI: 10.1007/BF01734359. View

Hohl M, Kurtz S, Ohlebusch E . Efficient multiple genome alignment. Bioinformatics. 2002; 18 Suppl 1:S312-20. DOI: 10.1093/bioinformatics/18.suppl_1.s312. View

Thorne J, Kishino H, Felsenstein J . An evolutionary model for maximum likelihood alignment of DNA sequences. J Mol Evol. 1991; 33(2):114-24. DOI: 10.1007/BF02193625. View

Thomas J, Touchman J, Blakesley R, Bouffard G, Beckstrom-Sternberg S, Margulies E . Comparative analyses of multi-species sequences from targeted genomic regions. Nature. 2003; 424(6950):788-93. DOI: 10.1038/nature01858. View

Loytynoja A, Milinkovitch M . A hidden Markov model for progressive multiple alignment. Bioinformatics. 2003; 19(12):1505-13. DOI: 10.1093/bioinformatics/btg193. View

Gotoh O . Optimal alignment between groups of sequences and its application to multiple sequence alignment. Comput Appl Biosci. 1993; 9(3):361-70. DOI: 10.1093/bioinformatics/9.3.361. View

Bray N, Pachter L . MAVID multiple alignment server. Nucleic Acids Res. 2003; 31(13):3525-6. PMC: 169029. DOI: 10.1093/nar/gkg623. View

Gotoh O . Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. J Mol Biol. 1996; 264(4):823-38. DOI: 10.1006/jmbi.1996.0679. View

10.

Myers G, Selznick S, Zhang Z, Miller W . Progressive multiple alignment with constraints. J Comput Biol. 1996; 3(4):563-72. DOI: 10.1089/cmb.1996.3.563. View

11.

Notredame C . Recent progress in multiple sequence alignment: a survey. Pharmacogenomics. 2002; 3(1):131-44. DOI: 10.1517/14622416.3.1.131. View

12.

Kent W . BLAT--the BLAST-like alignment tool. Genome Res. 2002; 12(4):656-64. PMC: 187518. DOI: 10.1101/gr.229202. View

13.

Feng D, Doolittle R . Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol. 1987; 25(4):351-60. DOI: 10.1007/BF02603120. View

14.

Hein J . An algorithm for statistical alignment of sequences related by a binary tree. Pac Symp Biocomput. 2001; :179-90. DOI: 10.1142/9789814447362_0019. View

15.

Brudno M, Do C, Cooper G, Kim M, Davydov E, Green E . LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA. Genome Res. 2003; 13(4):721-31. PMC: 430158. DOI: 10.1101/gr.926603. View

16.

Olsen G, Matsuda H, Hagstrom R, Overbeek R . fastDNAmL: a tool for construction of phylogenetic trees of DNA sequences using maximum likelihood. Comput Appl Biosci. 1994; 10(1):41-8. DOI: 10.1093/bioinformatics/10.1.41. View

17.

Slowinski J . The number of multiple alignments. Mol Phylogenet Evol. 1999; 10(2):264-6. DOI: 10.1006/mpev.1998.0522. View

18.

Bray N, Dubchak I, Pachter L . AVID: A global alignment program. Genome Res. 2003; 13(1):97-102. PMC: 430967. DOI: 10.1101/gr.789803. View

19.

Friedman N, Ninio M, Peer I, Pupko T . A structural EM algorithm for phylogenetic inference. J Comput Biol. 2002; 9(2):331-53. DOI: 10.1089/10665270252935494. View

20.

Yap V, Pachter L . Identification of evolutionary hotspots in the rodent genomes. Genome Res. 2004; 14(4):574-9. PMC: 383301. DOI: 10.1101/gr.1967904. View