{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T05:52:23Z","timestamp":1773294743168,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,11,9]],"date-time":"2012-11-09T00:00:00Z","timestamp":1352419200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1186\/1471-2105-13-293","type":"journal-article","created":{"date-parts":[[2012,11,9]],"date-time":"2012-11-09T15:14:18Z","timestamp":1352474058000},"source":"Crossref","is-referenced-by-count":28,"title":["The tree alignment problem"],"prefix":"10.1186","volume":"13","author":[{"given":"Andr\u00e9s","family":"Var\u00f3n","sequence":"first","affiliation":[]},{"given":"Ward C","family":"Wheeler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,11,9]]},"reference":[{"key":"5752_CR1","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions\u2013specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994, 22: 4673-4680. 10.1093\/nar\/22.22.4673.","journal-title":"Nucleic Acids Res"},{"key":"5752_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","volume":"15","author":"B Morgenstern","year":"1999","unstructured":"Morgenstern B: DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics. 1999, 15: 211-218. 10.1093\/bioinformatics\/15.3.211.","journal-title":"Bioinformatics"},{"key":"5752_CR3","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1093\/nar\/gkf436","volume":"30","author":"K Katoh","year":"2002","unstructured":"Katoh K, Misawa K, Kuma K, Miyata T: MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucl Acids Res. 2002, 30: 3059-3066. 10.1093\/nar\/gkf436.","journal-title":"Nucl Acids Res"},{"key":"5752_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1186\/1471-2105-5-113","volume":"5","author":"RC Edgar","year":"2004","unstructured":"Edgar RC: MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics. 2004, 5: 113-10.1186\/1471-2105-5-113. [ http:\/\/www.biomedcentral.com\/1471-2105\/6\/113 ]","journal-title":"BMC Bioinformatics"},{"issue":"4","key":"5752_CR5","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1080\/10635150590950371","volume":"54","author":"R Fleissner","year":"2005","unstructured":"Fleissner R, Metzler D, von Haeseler A: Simultaneous Statistical Multiple Alignment and Phylogeny Reconstruction. Syst Biol. 2005, 54 (4): 548-561. 10.1080\/10635150590950371.","journal-title":"Syst Biol"},{"key":"5752_CR6","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1080\/10635150590947041","volume":"54","author":"BD Redelings","year":"2005","unstructured":"Redelings BD, Suchard MA: Joint Bayesian Estimation of Alignment and Phylogeny. Syst Biol. 2005, 54: 401-418. 10.1080\/10635150590947041.","journal-title":"Syst Biol"},{"key":"5752_CR7","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1101\/gr.2821705","volume":"15","author":"CB Do","year":"2005","unstructured":"Do CB, Mahabhashyam MSP, Brudno M, Batzoglou S: ProbCons: Probabilistic consistency-based multiple sequence alignment. Genome Res. 2005, 15: 330-340. 10.1101\/gr.2821705.","journal-title":"Genome Res"},{"key":"5752_CR8","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1111\/j.1096-0031.2006.00096.x","volume":"22","author":"WC Wheeler","year":"2006","unstructured":"Wheeler WC: Dynamic Homology and the Likelihood Criterion. Cladistics. 2006, 22: 157-170. 10.1111\/j.1096-0031.2006.00096.x.","journal-title":"Cladistics"},{"key":"5752_CR9","first-page":"25","volume":"13","author":"S Nelesen","year":"2008","unstructured":"Nelesen S, Liu K, Zhao D, Linder CR, Warnow T: The effect of the guide tree on multiple sequence alignments and subsequenct phylogenetic analyses. Pac Symp Biocomputing. 2008, 13: 25-36.","journal-title":"Pac Symp Biocomputing"},{"key":"5752_CR10","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D Sankoff","year":"1975","unstructured":"Sankoff D: Minimal Mutation Trees of Sequences. SIAM J Appl Mathematics. 1975, 28: 35-42. 10.1137\/0128004.","journal-title":"SIAM J Appl Mathematics"},{"key":"5752_CR11","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01732471","volume":"7","author":"D Sankoff","year":"1976","unstructured":"Sankoff D, Cedergren RJ, Lapalme G: Frequency of Insertion-Deletion, Transversion, and Transition in the Evolution of 5S Ribosomal RNA. J Mol Evol. 1976, 7: 133-149. 10.1007\/BF01732471.","journal-title":"J Mol Evol"},{"key":"5752_CR12","volume-title":"Simultaneous Comparison of Three or more Sequences Related by a Tree","author":"D Sankoff","year":"1983:","unstructured":"Sankoff D, Cedergren RJ: Simultaneous Comparison of Three or more Sequences Related by a Tree. 1983:, Addison-Wesley: Reading, MA, 253\u2013263"},{"issue":"6","key":"5752_CR13","first-page":"649","volume":"6","author":"J Hein","year":"1989","unstructured":"Hein J: A New Method That Simultaneously Aligns and Reconstructs Ancestral Sequences for Any Number of Homologous Sequences, When The Phylogeny is Given. Mol Biol Evol. 1989, 6 (6): 649-668.","journal-title":"Mol Biol Evol"},{"key":"5752_CR14","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1016\/0076-6879(90)83041-7","volume":"183","author":"J Hein","year":"1990","unstructured":"Hein J: Unified approach to alignment and phylogenies. Methods in Enzymology. 1990, 183: 626-645.","journal-title":"Methods in Enzymology"},{"key":"5752_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1096-0031.1996.tb00189.x","volume":"12","author":"WC Wheeler","year":"1996","unstructured":"Wheeler WC: Optimization Alignment: The End of Multiple Sequence Alignment in Phylogenetics?. Cladistics. 1996, 12: 1-9. 10.1111\/j.1096-0031.1996.tb00189.x.","journal-title":"Cladistics"},{"key":"5752_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1186\/1471-2105-7-527","volume":"7","author":"RA Cartwright","year":"2006","unstructured":"Cartwright RA: Logarithmic gap costs decrease alignment accuracy. BMC Bioinformatics. 2006, 7: 527-539. 10.1186\/1471-2105-7-527.","journal-title":"BMC Bioinformatics"},{"key":"5752_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1109\/TCBB.2008.63","volume":"6","author":"K Liu","year":"2009","unstructured":"Liu K, Nelesen S, Raghavan S, Linder CR, Warnow T: Barking up the wrong treelength: the impact of gap penalty on alignment and tree accuracy. IEEE Trans Comput Biol Bioinf. 2009, 6: 7-21.","journal-title":"IEEE Trans Comput Biol Bioinf"},{"issue":"3","key":"5752_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","volume":"20","author":"MS Waterman","year":"1976","unstructured":"Waterman MS, Smith TF, Beyer WA: Some biological sequence metrics. Advances in Mathematics. 1976, 20 (3): 367-387. 10.1016\/0001-8708(76)90202-4. [ http:\/\/www.sciencedirect.com\/science\/article\/B6W9F-4CRY72S-1TG\/1\/ad09f046408307294171dca4c664d801 ]","journal-title":"Advances in Mathematics"},{"key":"5752_CR19","first-page":"1065","volume":"229","author":"SA Benner","year":"1993","unstructured":"Benner SA, Cohen MA: Empirical and structural models for insertions and deletions in the divergent evolution of proteins. J Mol Evol. 1993, 229: 1065-1082.","journal-title":"J Mol Evol"},{"issue":"4","key":"5752_CR20","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF00164032","volume":"40","author":"X Gu","year":"1995","unstructured":"Gu X, Li WH: The size distribution of insertions and deletions in human and rodent pseudogenes suggests the logarithmic gap penalty for sequence alignment. J Mol Evol. 1995, 40 (4): 464-473. 10.1007\/BF00164032. [ http:\/\/dx.doi.org\/10.1007\/BF00164032 ]","journal-title":"J Mol Evol"},{"issue":"18","key":"5752_CR21","doi-asserted-by":"publisher","first-page":"5338","DOI":"10.1093\/nar\/gkg745","volume":"31","author":"Z Zhang","year":"2003","unstructured":"Zhang Z, Gerstein M: Patterns of nucleotide substitution, insertion and deletion in the human genome inferred from pseudogenes. Nucl Acids Res. 2003, 31 (18): 5338-5348. 10.1093\/nar\/gkg745. [ http:\/\/nar.oxfordjournals.org\/cgi\/content\/abstract\/31\/18\/5338 ]","journal-title":"Nucl Acids Res"},{"issue":"2","key":"5752_CR22","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.jmb.2004.05.045","volume":"341","author":"MSS Chang","year":"2004","unstructured":"Chang MSS, Benner SA: Empirical Analysis of Protein Insertions and Deletions Determining Parameters for the Correct Placement of Gaps in Protein Sequence Alignments. J Mol Biol. 2004, 341 (2): 617-631. 10.1016\/j.jmb.2004.05.045. [ http:\/\/www.sciencedirect.com\/science\/article\/B6WK7-4CMHDHJ-6\/2\/9cbe746387e0610d53e294114342f02c ]","journal-title":"J Mol Biol"},{"key":"5752_CR23","volume-title":"POY, Phylogeny Reconstruction via Optimization of DNA and other Data version 3.0.11 (May 6 of 2003)","author":"WC Wheeler","year":"2003","unstructured":"Wheeler WC, Gladstein D: POY, Phylogeny Reconstruction via Optimization of DNA and other Data version 3.0.11 (May 6 of 2003). 2003, American Museum of Natural History, [ ftp:\/\/ftp.amnh.org ]"},{"key":"5752_CR24","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1111\/j.1096-0031.2009.00282.x","volume":"26","author":"A Var\u00f3n","year":"2009","unstructured":"Var\u00f3n A, Vinh LS, Wheeler WC: POY version 4: phylogenetic analysis using dynamic homologies. Cladistics. 2009, 26: 72-85.","journal-title":"Cladistics"},{"key":"5752_CR25","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/3-540-48452-3_8","volume":"1645","author":"G Lancia","year":"1999","unstructured":"Lancia G, Ravi R: GESTALT: Genomic steiner alignments. Lecture Notes in Computer Science. 1999, 1645: 101-10.1007\/3-540-48452-3_8.","journal-title":"Lecture Notes in Computer Science"},{"key":"5752_CR26","volume-title":"SALSA: Sequence alignment via Steiner Ancestors","author":"G Lancia","year":"2008","unstructured":"Lancia G, Ravi R: SALSA: Sequence alignment via Steiner Ancestors. 2008, [ http:\/\/citeseer.ist.psu.edu\/356333.html ]"},{"key":"5752_CR27","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0166-218X(02)00288-3","volume":"127","author":"B Schwikowski","year":"2003","unstructured":"Schwikowski B, Vingron M: Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions. Discrete Appl Math. 2003, 127: 95-117. 10.1016\/S0166-218X(02)00288-3.","journal-title":"Discrete Appl Math"},{"issue":"2","key":"5752_CR28","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1080\/10635150701281102","volume":"56","author":"TH Ogden","year":"2007","unstructured":"Ogden TH, Rosenberg MS: Alignment and Topological Accuracy of the Direct Optimization approach via POY and Traditional Phylogenetics via ClustalW + PAUP*. Syst Biol. 2007, 56 (2): 182-193. 10.1080\/10635150701281102.","journal-title":"Syst Biol"},{"issue":"4","key":"5752_CR29","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1080\/10635150802302476","volume":"57","author":"S Lehtonen","year":"2008","unstructured":"Lehtonen S: Phylogeny Estimation and Alignment via POY versus Clustal + PAUP*: A Response to Ogden and Rosenberg (2007). Syst Biol. 2008, 57 (4): 653-657. 10.1080\/10635150802302476.","journal-title":"Syst Biol"},{"key":"5752_CR30","volume-title":"Sequence Alignment, edited by M. S. Rosenberg","author":"WC Wheeler","year":"2009","unstructured":"Wheeler WC: Sequence Alignment, edited by M. S. Rosenberg. 2009, Berkeley, CA, USA: University of California Press, chap. Simulation Approaches to Evaluating Alignment Error and Methods for Comparing Alternate Alignments: 179\u2013208"},{"key":"5752_CR31","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang L, Jiang T: On the Complexity of Multiple Sequence Alignment. J Comput Biol. 1994, 1: 337-348. 10.1089\/cmb.1994.1.337.","journal-title":"J Comput Biol"},{"issue":"Suppl 1","key":"5752_CR32","doi-asserted-by":"publisher","first-page":"S11","DOI":"10.1186\/1471-2105-10-S1-S11","volume":"10","author":"F Yue","year":"2009","unstructured":"Yue F, Shi J, Tang J: Simultaneous phylogeny reconstruction and multiple sequence alignment. BMC Bioinf. 2009, 10 (Suppl 1): S11-10.1186\/1471-2105-10-S1-S11.","journal-title":"BMC Bioinf"},{"key":"5752_CR33","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1145\/267521.267884","volume-title":"RECOMB \u201997: Proceedings of the first annual international conference on Computational molecular biology","author":"B Schwikowski","year":"1997","unstructured":"Schwikowski B, Vingron M: The deferred path heuristic for the generalized tree alignment problem. RECOMB \u201997: Proceedings of the first annual international conference on Computational molecular biology. 1997, New York, NY, USA: ACM Press, 257-266. [ http:\/\/doi.acm.org\/10.1145\/267521.267884 ]"},{"key":"5752_CR34","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01955679","volume":"16","author":"L Wang","year":"1996","unstructured":"Wang L, Jiang T, Lawler EL: Approximation Algorithms for Tree Alignment with a Given Phylogeny. Algorithmica. 1996, 16: 302-315.","journal-title":"Algorithmica"},{"issue":"2","key":"5752_CR35","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jagm.1997.0882","volume":"25","author":"L Wang","year":"1997","unstructured":"Wang L, Gusfield D: Impoved Approximation Algorithms for Tree Alignment. J Algorithms. 1997, 25 (2): 255-273. 10.1006\/jagm.1997.0882.","journal-title":"J Algorithms"},{"key":"5752_CR36","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0166-218X(98)00079-1","volume":"88","author":"R Ravi","year":"1998","unstructured":"Ravi R, Kececioglu JD: Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree. Discret Appl Math. 1998, 88: 355-366. 10.1016\/S0166-218X(98)00079-1.","journal-title":"Discret Appl Math"},{"key":"5752_CR37","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1137\/S0097539796313507","volume":"30","author":"L Wang","year":"2000","unstructured":"Wang L, Jiang T, Gusfield D: A More Efficient Approximation Scheme for Tree Alignment. SIAM J Comput. 2000, 30: 283-299. 10.1137\/S0097539796313507.","journal-title":"SIAM J Comput"},{"key":"5752_CR38","volume-title":"Dynamic Homology and Phylogenetic Systematics: A Unified Approach using POY","author":"WC Wheeler","year":"2006","unstructured":"Wheeler WC, Aagesen L, Arango CP, Faivovich J, Grant T, D\u2019Haese C, Janies D, Smith WL, Var\u00f3n A, Giribet G: Dynamic Homology and Phylogenetic Systematics: A Unified Approach using POY. 2006 pp. 365, American Museum of Natural History"},{"key":"5752_CR39","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. J Mol Biol. 1970, 48: 443-453. 10.1016\/0022-2836(70)90057-4.","journal-title":"J Mol Biol"},{"key":"5752_CR40","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. J Mol Biol. 1982, 162: 705-708. 10.1016\/0022-2836(82)90398-9.","journal-title":"J Mol Biol"},{"issue":"1-3","key":"5752_CR41","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen E: Algorithms for approximate string matching. Inf Control. 1985, 64 (1-3): 100-118. 10.1016\/S0019-9958(85)80046-2.","journal-title":"Inf Control"},{"issue":"Suppl. 3","key":"5752_CR42","doi-asserted-by":"crossref","first-page":"iii31","DOI":"10.1093\/bioinformatics\/bti1200","volume":"21","author":"Cartwright R A","year":"2005","unstructured":"Cartwright R A: DNA Assembly with gaps (Dawg): simulating sequence evolution. Bioinformatics. 2005, 21 (Suppl. 3): iii31-iii38.","journal-title":"Bioinformatics"},{"key":"5752_CR43","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1111\/j.1096-0031.1999.tb00274.x","volume":"15","author":"WC Wheeler","year":"1999","unstructured":"Wheeler WC: Fixed Character States and the Optimization of Molecular Sequence Data. Cladistics. 1999, 15: 379-385. 10.1111\/j.1096-0031.1999.tb00274.x.","journal-title":"Cladistics"},{"key":"5752_CR44","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1006\/jtbi.2000.2177","volume":"207","author":"DR Powell","year":"2000","unstructured":"Powell DR, Allison L, Dix TI: Fast optimal alignment of three sequences using linear gap costs. J Theor Biol. 2000, 207: 325-336. 10.1006\/jtbi.2000.2177.","journal-title":"J Theor Biol"},{"key":"5752_CR45","doi-asserted-by":"crossref","unstructured":"Yue F, Tang J: A divide-and-conquer implementation of three sequence alignment and ancestor inference with affine gap costs. The IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2007),. 143-150.","DOI":"10.1109\/BIBM.2007.40"},{"issue":"6","key":"5752_CR46","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1111\/j.1096-0031.2008.00208.x","volume":"24","author":"A Var\u00f3n","year":"2008","unstructured":"Var\u00f3n A, Wheeler WC: Application note: on extension gap in POY version 3. Cladistics. 2008, 24 (6): 1070-1070. 10.1111\/j.1096-0031.2008.00208.x.","journal-title":"Cladistics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-293.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-13-293\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-293.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T18:13:41Z","timestamp":1687803221000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,9]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5752"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-293","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,9]]},"article-number":"293"}}