{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T12:16:35Z","timestamp":1774786595803,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Multiple genome alignment is an important problem in bioinformatics. An important subproblem used by many multiple alignment approaches is that of aligning two multiple alignments. Many popular alignment algorithms for DNA use the sum-of-pairs heuristic, where the score of a multiple alignment is the sum of its induced pairwise alignment scores. However, the biological meaning of the sum-of-pairs of pairs heuristic is not obvious. Additionally, many algorithms based on the sum-of-pairs heuristic are complicated and slow, compared to pairwise alignment algorithms.<\/jats:p>\n                <jats:p>An alternative approach to aligning alignments is to first infer ancestral sequences for each alignment, and then align the two ancestral sequences. In addition to being fast, this method has a clear biological basis that takes into account the evolution implied by an underlying phylogenetic tree.<\/jats:p>\n                <jats:p>In this study we explore the accuracy of aligning alignments by ancestral sequence alignment. We examine the use of both maximum likelihood and parsimony to infer ancestral sequences. Additionally, we investigate the effect on accuracy of allowing ambiguity in our ancestral sequences.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We use synthetic sequence data that we generate by simulating evolution on a phylogenetic tree. We use two different types of phylogenetic trees: trees with a period of rapid growth followed by a period of slow growth, and trees with a period of slow growth followed by a period of rapid growth.<\/jats:p>\n                <jats:p>We examine the alignment accuracy of four ancestral sequence reconstruction and alignment methods: parsimony, maximum likelihood, ambiguous parsimony, and ambiguous maximum likelihood. Additionally, we compare against the alignment accuracy of two sum-of-pairs algorithms: ClustalW and the heuristic of Ma, Zhang, and Wang.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>We find that allowing ambiguity in ancestral sequences does not lead to better multiple alignments. Regardless of whether we use parsimony or maximum likelihood, the success of aligning ancestral sequences containing ambiguity is very sensitive to the choice of gap open cost. Surprisingly, we find that using maximum likelihood to infer ancestral sequences results in less accurate alignments than when using parsimony to infer ancestral sequences. Finally, we find that the sum-of-pairs methods produce better alignments than all of the ancestral alignment methods.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/1471-2105-6-273","type":"journal-article","created":{"date-parts":[[2005,11,17]],"date-time":"2005-11-17T19:14:21Z","timestamp":1132254861000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Ancestral sequence alignment under optimal conditions"],"prefix":"10.1186","volume":"6","author":[{"given":"Alexander K","family":"Hudek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel G","family":"Brown","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,11,17]]},"reference":[{"key":"598_CR1","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1101\/gr.1960404","volume":"14","author":"N Bray","year":"2004","unstructured":"Bray N, Pachter L: MAVID: Constrained Ancestral Alignment of Multiple Sequences. Genome Research 2004, 14: 693\u2013699.","journal-title":"Genome Research"},{"key":"598_CR2","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1101\/gr.926603","volume":"13","author":"M Brudno","year":"2003","unstructured":"Brudno M, Do C, Cooper G, Kim M, et al.: LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA. Genome Research 2003, 13: 721\u2013731.","journal-title":"Genome Research"},{"issue":"4","key":"598_CR3","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D Feng","year":"1987","unstructured":"Feng D, Doolittle R: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. Journal of Molecular Evolution 1987, 25(4):351\u2013360.","journal-title":"Journal of Molecular Evolution"},{"issue":"6","key":"598_CR4","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1089\/106652701753307511","volume":"8","author":"W Just","year":"2001","unstructured":"Just W: Computational Complexity of Multiple Sequence Alignment with SP-Score. Journal of Computational Biology 2001, 8(6):615\u2013623.","journal-title":"Journal of Computational Biology"},{"key":"598_CR5","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J Thompson","year":"1994","unstructured":"Thompson J, Higgins D, Gibson T: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research 1994, 22: 4673\u20134680.","journal-title":"Nucleic Acids Research"},{"key":"598_CR6","first-page":"254","volume-title":"Proceedings of CPM 2003","author":"B Ma","year":"2003","unstructured":"Ma B, Wang Z, Zhang K: Alignment between Two Multiple Alignments. In Proceedings of CPM 2003. Springer-Verlag; 2003:254\u2013265."},{"key":"598_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1145\/974614.974626","volume-title":"RECOMB '04: Proceedings of the eighth annual international conference on Computational molecular biology","author":"J Kececioglu","year":"2004","unstructured":"Kececioglu J, Starrett D: Aligning alignments exactly. In RECOMB '04: Proceedings of the eighth annual international conference on Computational molecular biology. New York, NY, USA: ACM Press; 2004:85\u201396."},{"key":"598_CR8","first-page":"314","volume":"3240","author":"DG Brown","year":"2004","unstructured":"Brown DG, Hudek AK: New Algorithms for Multiple DNA Sequence Alignment. Proceedings of WABI 2003 2004, 3240: 314\u2013325.","journal-title":"Proceedings of WABI 2003"},{"issue":"2","key":"598_CR9","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1093\/jhered\/92.2.212","volume":"92","author":"E Eizirik","year":"2001","unstructured":"Eizirik E, Murphy W, O'Brien S: Molecular Dating and Biogeography of the Early Placental Mammal Radiation. The Journal of Heredity 2001, 92(2):212\u2013219.","journal-title":"The Journal of Heredity"},{"key":"598_CR10","volume-title":"Phyl-O-Gen v1.2","author":"A Rambaut","year":"2003","unstructured":"Rambaut A: Phyl-O-Gen v1.2.2003. [http:\/\/evolve.zoo.ox.ac.uk\/]"},{"key":"598_CR11","first-page":"177","volume-title":"Proceedings of WABI 2003","author":"P Kearney","year":"2003","unstructured":"Kearney P, Munro I, Phillips D: Efficient Generation of Uniform Samples from Phylogenetic Trees. In Proceedings of WABI 2003. Benson G, Page R; 2003:177\u2013189."},{"issue":"2","key":"598_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1093\/bioinformatics\/14.2.157","volume":"14","author":"J Stoye","year":"1998","unstructured":"Stoye J, Evers D, Meyer F: Rose: generating sequence families. Bioinformatics 1998, 14(2):157\u2013163.","journal-title":"Bioinformatics"},{"key":"598_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological sequence analysis. Cambridge University Press; 1998."},{"issue":"6950","key":"598_CR14","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1038\/nature01858","volume":"424","author":"J Thomas","year":"2003","unstructured":"Thomas J, Touchman J, Blakesley R, Bouffard G, Beckstrom-Sternberg S, Margulies E, Blanchette M, Siepel A, Thomas P, McDowell J, Maskeri B, Hansen N, Schwartz M, Weber R, Kent W, Karolchik D, Bruen T, Bevan R, Cutler D, Schwartz S, Elnitski L, Idol J, Prasad A, Lee-Lin S, Maduro V, Summers T, Portnoy M, Dietrich N, Akhter N, Ayele K, Benjamin B, Cariaga K, Brinkley C, Brooks S, Granite S, Guan X, Gupta J, Haghighi P, Ho S, Huang M, Karlins E, Laric P, Legaspi R, Lim M, Maduro Q, Masiello C, Mastrian S, McCloskey J, Pearson R, Stantripop S, Tiongson E, Tran J, Tsurgeon C, Vogt J, Walker M, Wetherby K, Wiggins L, Young A, Zhang L, Osoegawa K, Zhu B, Zhao B, Shu C, Jong PD, Lawrence C, Smit A, Chakravarti A, Haussler D, Green P, Miller W, Green E: Comparative analyses of multi-species sequences from targeted genomic regions. Nature 2003, 424(6950):788\u2013793.","journal-title":"Nature"},{"key":"598_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1086\/302218","volume":"64","author":"M Goodman","year":"1999","unstructured":"Goodman M: The genomic record of Humankind's evolutionary roots. American Journal of Human Genetics 1999, 64: 31\u201339.","journal-title":"American Journal of Human Genetics"},{"key":"598_CR16","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S Needleman","year":"1970","unstructured":"Needleman S, Wunsch C: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 1970, 48: 443\u2013453.","journal-title":"Journal of Molecular Biology"},{"key":"598_CR17","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O: An improved algorithm for matching biological sequences. Journal of Molecular Biology 1982, 162: 705\u2013708.","journal-title":"Journal of Molecular Biology"},{"key":"598_CR18","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"W Fitch","year":"1971","unstructured":"Fitch W: Toward defining the course of evolution: minimum change for a specified tree topology. Systematic Zoology 1971, 20: 406\u2013416.","journal-title":"Systematic Zoology"},{"key":"598_CR19","volume-title":"Master's thesis","author":"AK Hudek","year":"2004","unstructured":"Hudek AK: New Anchoring Techniques for Global Multiple Alignment of Genomic Sequences. In Master's thesis. University of Waterloo; 2004."},{"key":"598_CR20","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2003","unstructured":"Felsenstein J: Inferring Phylogenies. Sinauer Associates; 2003."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-273.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:57:29Z","timestamp":1706810249000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,17]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["598"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-273","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11,17]]},"assertion":[{"value":"28 July 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"273"}}