{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T21:02:34Z","timestamp":1778360554322,"version":"3.51.4"},"reference-count":41,"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>Two central problems in computational biology are the determination of the alignment and phylogeny of a set of biological sequences. The traditional approach to this problem is to first build a multiple alignment of these sequences, followed by a phylogenetic reconstruction step based on this multiple alignment. However, alignment and phylogenetic inference are fundamentally interdependent, and ignoring this fact leads to biased and overconfident estimations. Whether the main interest be in sequence alignment or phylogeny, a major goal of computational biology is the co-estimation of both.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We developed a fully Bayesian Markov chain Monte Carlo method for coestimating phylogeny and sequence alignment, under the Thorne-Kishino-Felsenstein model of substitution and single nucleotide insertion-deletion (indel) events. In our earlier work, we introduced a novel and efficient algorithm, termed the \"indel peeling algorithm\", which includes indels as phylogenetically informative evolutionary events, and resembles Felsenstein's peeling algorithm for substitutions on a phylogenetic tree. For a fixed alignment, our extension analytically integrates out both substitution and indel events within a proper statistical model, without the need for data augmentation at internal tree nodes, allowing for efficient sampling of tree topologies and edge lengths. To additionally sample multiple alignments, we here introduce an efficient partial Metropolized independence sampler for alignments, and combine these two algorithms into a fully Bayesian co-estimation procedure for the alignment and phylogeny problem.<\/jats:p>\n                <jats:p>Our approach results in estimates for the posterior distribution of evolutionary rate parameters, for the maximum <jats:italic>a-posteriori<\/jats:italic> (MAP) phylogenetic tree, and for the posterior decoding alignment. Estimates for the evolutionary tree and multiple alignment are augmented with confidence estimates for each node height and alignment column. Our results indicate that the patterns in reliability broadly correspond to structural features of the proteins, and thus provides biologically meaningful information which is not existent in the usual point-estimate of the alignment. Our methods can handle input data of moderate size (10\u201320 protein sequences, each 100\u2013200 bp), which we analyzed overnight on a standard 2 GHz personal computer.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>Joint analysis of multiple sequence alignment, evolutionary trees and additional evolutionary parameters can be now done within a single coherent statistical framework.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/1471-2105-6-83","type":"journal-article","created":{"date-parts":[[2005,4,2]],"date-time":"2005-04-02T06:14:11Z","timestamp":1112422451000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":120,"title":["Bayesian coestimation of phylogeny and sequence alignment"],"prefix":"10.1186","volume":"6","author":[{"given":"Gerton","family":"Lunter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Mikl\u00f3s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexei","family":"Drummond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens Ledet","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jotun","family":"Hein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,4,1]]},"reference":[{"key":"408_CR1","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 multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choise. Nucleic Acids Res 1994, 22: 4673\u20134680.","journal-title":"Nucleic Acids Res"},{"key":"408_CR2","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins D, Heringa J: T-Coffee: A novel method for multiple sequence alignments. Journal of Molecular Biology 2000, 302: 205\u2013217. 10.1006\/jmbi.2000.4042","journal-title":"Journal of Molecular Biology"},{"key":"408_CR3","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1093\/bioinformatics\/17.8.754","volume":"17","author":"JP Huelsenbeck","year":"2001","unstructured":"Huelsenbeck JP, Ronquist F: MRBAYES: Bayesian inference of phylogenetic trees. Bioinformatics 2001, 17: 754\u2013755. 10.1093\/bioinformatics\/17.8.754","journal-title":"Bioinformatics"},{"key":"408_CR4","volume-title":"Sinauer Associates","author":"D Swofford","year":"2001","unstructured":"Swofford D: PAUP* 4.0. Sinauer Associates 2001."},{"key":"408_CR5","volume-title":"Dept of Genetics, Univ of Washington, Seattle","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J: PHYLIP version 3.63. Dept of Genetics, Univ of Washington, Seattle 2004."},{"key":"408_CR6","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1038\/newbio245232a0","volume":"245","author":"D Sankoff","year":"1973","unstructured":"Sankoff D, Morel C, J CR: Evolution of 5S RNA and the non-randomness of base replacement. Nature New Biology 1973, 245: 232\u2013234.","journal-title":"Nature New Biology"},{"key":"408_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","volume-title":"Mammalian Protein Metabolism","author":"TH Jukes","year":"1969","unstructured":"Jukes TH, Cantor CR: Evolution of Protein Molecules. In Mammalian Protein Metabolism. Edited by: Munro. Acad Press; 1969:21\u2013132."},{"key":"408_CR8","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/S0168-9525(01)02272-7","volume":"17","author":"S Whelan","year":"2001","unstructured":"Whelan S, Li\u00f3 P, Goldman N: Molecular phylogenetics: state-of-the-art methods for looking into the past. Trends in Gen 2001, 17: 262\u2013272. 10.1016\/S0168-9525(01)02272-7","journal-title":"Trends in Gen"},{"key":"408_CR9","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0022-2836(86)90289-5","volume":"190","author":"M Bishop","year":"1986","unstructured":"Bishop M, Thompson E: Maximum likelihood alignment of DNA sequences. J Mol Biol 1986, 190: 159\u2013165. 10.1016\/0022-2836(86)90289-5","journal-title":"J Mol Biol"},{"key":"408_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/BF02193625","volume":"33","author":"JL Thorne","year":"1991","unstructured":"Thorne JL, Kishino H, Felsenstein J: An Evolutionary Model for Maximum Likelihood Alignment of DNA Sequences. J Mol Evol 1991, 33: 114\u2013124.","journal-title":"J Mol Evol"},{"key":"408_CR11","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/S0893-9659(01)80026-4","volume":"14","author":"M Steel","year":"2001","unstructured":"Steel M, Hein J: Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree. Appl Math Let 2001, 14: 679\u2013684. 10.1016\/S0893-9659(01)80026-4","journal-title":"Appl Math Let"},{"key":"408_CR12","first-page":"179","volume-title":"Pac Symp Biocomp, World Scientific","author":"J Hein","year":"2001","unstructured":"Hein J: An algorithm for statistical alignment of sequences related by a binary tree. Pac Symp Biocomp, World Scientific 2001, 179\u2013190."},{"issue":"9","key":"408_CR13","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1093\/bioinformatics\/17.9.803","volume":"17","author":"I Holmes","year":"2001","unstructured":"Holmes I, Bruno WJ: Evolutionary HMMs: a Bayesian approach to multiple alignment. Bioinformatics 2001, 17(9):803\u2013820. 10.1093\/bioinformatics\/17.9.803","journal-title":"Bioinformatics"},{"issue":"25","key":"408_CR14","doi-asserted-by":"publisher","first-page":"14960","DOI":"10.1073\/pnas.2036252100","volume":"100","author":"J Hein","year":"2003","unstructured":"Hein J, Jensen JL, Pedersen CNS: Recursions for statistical multiple alignment. PNAS 2003, 100(25):14960\u201314965. 10.1073\/pnas.2036252100","journal-title":"PNAS"},{"key":"408_CR15","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1006\/bulm.2002.0300","volume":"64","author":"I Mikl\u00f3s","year":"2002","unstructured":"Mikl\u00f3s I: An Improved Algorithm for Statistical Alignment of Sequences related by a Star Tree. Bul Math Biol 2002, 64: 771\u2013779. 10.1006\/bulm.2002.0300","journal-title":"Bul Math Biol"},{"issue":"6","key":"408_CR16","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1089\/106652703322756122","volume":"10","author":"G Lunter","year":"2003","unstructured":"Lunter G, Mikl\u00f3s I, Song Y, Hein J: An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. J Comp Biol 2003, 10(6):869\u2013889. 10.1089\/106652703322756122","journal-title":"J Comp Biol"},{"issue":"3","key":"408_CR17","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1093\/molbev\/msh043","volume":"21","author":"I Mikl\u00f3s","year":"2004","unstructured":"Mikl\u00f3s I, Lunter GA, Holmes I: A \"Long Indel\" model for evolutionary sequence alignment. Mol Biol Evol 2004, 21(3):529\u2013540. 10.1093\/molbev\/msh043","journal-title":"Mol Biol Evol"},{"key":"408_CR18","doi-asserted-by":"crossref","unstructured":"Holmes I: A probabilistic model for the evolution of RNA structure. BMC Bioinf 2004., 5(166):","DOI":"10.1186\/1471-2105-5-166"},{"issue":"4","key":"408_CR19","doi-asserted-by":"crossref","first-page":"1421","DOI":"10.1093\/genetics\/140.4.1421","volume":"140","author":"MK Kuhner","year":"1995","unstructured":"Kuhner MK, Yamato J, Felsenstein J: Estimating effective population size and mutation rate from sequence data using Metropolis-Hastings sampling. Genetics 1995, 140(4):1421\u20131430.","journal-title":"Genetics"},{"key":"408_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1214\/ss\/1177010378","volume":"9","author":"RC Griffiths","year":"1994","unstructured":"Griffiths RC, Tavare S: Ancestral inference in population genetics. Stat Sci 1994, 9: 307\u2013319.","journal-title":"Stat Sci"},{"key":"408_CR21","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1093\/genetics\/150.1.499","volume":"150","author":"IJ Wilson","year":"1998","unstructured":"Wilson IJ, Balding DJ: Genealogical Inference From Microsatellite Data. Genetics 1998, 150: 499\u2013450.","journal-title":"Genetics"},{"issue":"3","key":"408_CR22","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1093\/genetics\/161.3.1307","volume":"161","author":"AJ Drummond","year":"2002","unstructured":"Drummond AJ, Nicholls GK, Rodrigo AG, Solomon W: Estimating mutation parameters, population history and genealogy simultaneously from temporally spaced sequence data. Genetics 2002, 161(3):1307\u20131320.","journal-title":"Genetics"},{"issue":"3","key":"408_CR23","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1093\/molbev\/msg043","volume":"20","author":"OG Pybus","year":"2003","unstructured":"Pybus OG, Drummond AJ, Nakano T, Robertson BH, Rambaut A: The epidemiology and iatrogenic transmission of hepatitis C virus in Egypt: a Bayesian coalescent approach. Mol Biol Evol 2003, 20(3):381\u2013387. 10.1093\/molbev\/msg043","journal-title":"Mol Biol Evol"},{"key":"408_CR24","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1017\/S0016672300030354","volume":"59","author":"J Felsenstein","year":"1992","unstructured":"Felsenstein J: Estimating effective population size from samples of sequences: Inefficiency of pairwise and segregating sites as compared to phylogenetic estimates. Genetical Research Cambridge 1992, 59: 139\u2013147.","journal-title":"Genetical Research Cambridge"},{"key":"408_CR25","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1111\/1467-9868.00254","volume":"62","author":"M Stephens","year":"2000","unstructured":"Stephens M, Donnelly P: Inference in Molecular Population Genetics. J of the Royal Stat Soc B 2000, 62: 605\u2013655. 10.1111\/1467-9868.00254","journal-title":"J of the Royal Stat Soc B"},{"issue":"3","key":"408_CR26","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1093\/genetics\/155.3.1429","volume":"155","author":"OG Pybus","year":"2000","unstructured":"Pybus OG, Rambaut A, Harvey PH: An integrated framework for the inference of viral population history from reconstructed genealogies. Genetics 2000, 155(3):1429\u20131437.","journal-title":"Genetics"},{"key":"408_CR27","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01734359","volume":"17","author":"J Felsenstein","year":"1981","unstructured":"Felsenstein J: Evolutionary trees from DNA sequences: a maximum likelihood approach. J Mol Evol 1981, 17: 368\u2013376.","journal-title":"J Mol Evol"},{"key":"408_CR28","volume-title":"Tech Rep 429, Dept of Theor Stat, U Aarhus","author":"J Jensen","year":"2002","unstructured":"Jensen J, Hein J: Gibbs sampler for statistical multiple alignment. Tech Rep 429, Dept of Theor Stat, U Aarhus 2002."},{"key":"408_CR29","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/s002390010253","volume":"53","author":"D Metzler","year":"2001","unstructured":"Metzler D, Flei\u00dfner R, Wakolbringer A, von Haeseler A: Assessing variability by joint sampling of alignments and mutation rates. J Mol Evol 2001, 53: 660\u2013669. 10.1007\/s002390010253","journal-title":"J Mol Evol"},{"issue":"4","key":"408_CR30","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1093\/bioinformatics\/btg026","volume":"19","author":"D Metzler","year":"2003","unstructured":"Metzler D: Statistical alignment based on fragment insertion and deletion models. Bioinformatics 2003, 19(4):490\u2013499. 10.1093\/bioinformatics\/btg026","journal-title":"Bioinformatics"},{"key":"408_CR31","first-page":"228","volume":"2812","author":"G Lunter","year":"2003","unstructured":"Lunter G, Mikl\u00f3s I, Drummond A, Jensen J, Hein J: Bayesian phylogenetic inference under a statistical indel model. Lecture Notes in Bioinformatics 2003, 2812: 228\u2013244.","journal-title":"Lecture Notes in Bioinformatics"},{"key":"408_CR32","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1093\/biomet\/83.1.81","volume":"83","author":"G Casella","year":"1996","unstructured":"Casella G, Robert CP: Rao-Blackwellisation of sampling schemes. Biometrika 1996, 83: 81\u201394. 10.1093\/biomet\/83.1.81","journal-title":"Biometrika"},{"key":"408_CR33","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jmbi.2000.4061","volume":"302","author":"J Hein","year":"2000","unstructured":"Hein J, Wiuf C, Knudsen B, M\u00f8ller MB, Wibling G: Statistical Alignment: Computational Properties, Homology Testing and Goodness-of-Fit. J Mol Biol 2000, 302: 265\u2013279. 10.1006\/jmbi.2000.4061","journal-title":"J Mol Biol"},{"key":"408_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44696-6_1","volume":"2149","author":"I Mikl\u00f3s","year":"2001","unstructured":"Mikl\u00f3s I, Toroczkai Z: An improved model for statistical alignment. Lecture Notes on Computer Science 2001, 2149: 1\u201310.","journal-title":"Lecture Notes on Computer Science"},{"issue":"4","key":"408_CR35","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0893-9659(98)00054-8","volume":"11","author":"A Dress","year":"1998","unstructured":"Dress A, Morgenstern B, Stoye J: The number of standard and of effective multiple alignments. App Math Lett 1998, 11(4):43\u201349. 10.1016\/S0893-9659(98)00054-8","journal-title":"App Math Lett"},{"key":"408_CR36","volume-title":"Monte Carlo Strategies in Scientific Computing","author":"JS Liu","year":"2001","unstructured":"Liu JS: Monte Carlo Strategies in Scientific Computing. Springer; 2001."},{"issue":"3","key":"408_CR37","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Meyer C, Steffen P: A Discipline of Dynamic Programming over Sequence Data. Science of Computer Programming 2004, 51(3):215\u2013263. 10.1016\/j.scico.2003.12.005","journal-title":"Science of Computer Programming"},{"key":"408_CR38","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."},{"key":"408_CR39","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","volume":"5","author":"I Holmes","year":"1998","unstructured":"Holmes I, Durbin R: Dynamic programming alignment accuracy. J Comp Biol 1998, 5: 493\u2013504.","journal-title":"J Comp Biol"},{"key":"408_CR40","volume-title":"BEAST v1.2.2","author":"AJ Drummond","year":"2004","unstructured":"Drummond AJ, Rambaut A: BEAST v1.2.2.2004. [http:\/\/evolve.zoo.ox.ac.uk\/beast]"},{"issue":"5404","key":"408_CR41","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1126\/science.283.5404.998","volume":"283","author":"SB Hedges","year":"1999","unstructured":"Hedges SB, Poling LL: A molecular phylogeny of reptiles. Science 1999, 283(5404):945\u2013946. 10.1126\/science.283.5404.998","journal-title":"Science"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-83.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:54:19Z","timestamp":1706810059000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4,1]]},"references-count":41,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["408"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-83","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,4,1]]},"assertion":[{"value":"20 January 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"83"}}