Bioinformatics Advance Access originally published online on January 22, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(3) © Oxford University Press 2004; all rights reserved.
Parallel Metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference
1 Department of Computer Science, University of Rochester, 2 Section of Ecology, Behavior and Evolution, Division of Biological Sciences, University of California, San Diego and 3 Department of Systematic Zoology, Evolutionary Biology Centre, Uppsala University
Received on August 29, 2002
; revised on April 3, 2003
; accepted on April 17, 2003
Advance Access Publication January 22, 2004
Motivation: Bayesian estimation of phylogeny is based on the posterior probability distribution of trees. Currently, the only numerical method that can effectively approximate posterior probabilities of trees is Markov chain Monte Carlo (MCMC). Standard implementations of MCMC can be prone to entrapment in local optima. Metropolis coupled MCMC [(MC)3], a variant of MCMC, allows multiple peaks in the landscape of trees to be more readily explored, but at the cost of increased execution time.
Results: This paper presents a parallel algorithm for (MC)3. The proposed parallel algorithm retains the ability to explore multiple peaks in the posterior distribution of trees while maintaining a fast execution time. The algorithm has been implemented using two popular parallel programming models: message passing and shared memory. Performance results indicate nearly linear speed improvement in both programming models for small and large data sets.
Availability: MrBayes v3.0 is available at http://morphbank.ebc.uu.se/mrbayes/
Contact: galtekar{at}cs.rochester.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. W. Brown, F. W. Spiegel, and J. D. Silberman Phylogeny of the "Forgotten" Cellular Slime Mold, Fonticula alba, Reveals a Key Evolutionary Branch within Opisthokonta Mol. Biol. Evol., December 1, 2009; 26(12): 2699 - 2709. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Simon, S. Strauss, A. von Haeseler, and H. Hadrys A Phylogenomic Approach to Resolve the Basal Pterygote Divergence Mol. Biol. Evol., December 1, 2009; 26(12): 2719 - 2730. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. M. Simon, S. A. Kelchner, and S. Zimmerly A Broadscale Phylogenetic Analysis of Group II Intron RNAs and Intron-Encoded Reverse Transcriptases Mol. Biol. Evol., December 1, 2009; 26(12): 2795 - 2808. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. W. Bloomquist and M. A. Suchard Unifying Vertical and Nonvertical Evolution: A Stochastic ARG-based Framework Syst Biol, November 9, 2009; (2009) syp076v1. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. J. Wurdack and C. C. Davis Malpighiales phylogenetics: Gaining ground on one of the most recalcitrant clades in the angiosperm tree of life Am. J. Botany, August 1, 2009; 96(8): 1551 - 1570. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. T. Cottrell and D. L. Kirchman Photoheterotrophic Microbes in the Arctic Ocean in Summer and Winter Appl. Envir. Microbiol., August 1, 2009; 75(15): 4958 - 4966. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. C. Brandley, D. L. Warren, A. D. Leache, and J. A. McGuire Homoplasy and Clade Support Syst Biol, June 29, 2009; (2009) syp019v1. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. E. Roberts, E. J. Sargis, and L. E. Olson Networks, Trees, and Treeshrews: Assessing Support and Identifying Conflict with Multiple Loci and a Problematic Root Syst Biol, June 16, 2009; (2009) syp025v3. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. M. Oliver, M. Adams, M. S.Y. Lee, M. N. Hutchinson, and P. Doughty Cryptic diversity in vertebrates: molecular data double estimates of species diversity in a radiation of Australian lizards (Diplodactylus, Gekkota) Proc R Soc B, June 7, 2009; 276(1664): 2001 - 2007. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. M. Labonte, K. E. Reid, and C. A. Suttle Phylogenetic Analysis Indicates Evolutionary Diversity and Environmental Segregation of Marine Podovirus DNA Polymerase Gene Sequences Appl. Envir. Microbiol., June 1, 2009; 75(11): 3634 - 3640. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. A. Suchard and A. Rambaut Many-core algorithms for statistical phylogenetics Bioinformatics, June 1, 2009; 25(11): 1370 - 1376. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. P. Der, J. A. Thomson, J. K. Stratford, and P. G. Wolf Global chloroplast phylogeny and biogeography of bracken (Pteridium; Dennstaedtiaceae) Am. J. Botany, May 1, 2009; 96(5): 1041 - 1049. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Timmins, S. R. Thomas-Hall, A. Darling, E. Zhang, B. Hankamer, U. C. Marx, and P. M. Schenk Phylogenetic and molecular analysis of hydrogen-producing green algae J. Exp. Bot., April 2, 2009; (2009) erp052v1. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Wang and B. Rannala Bayesian inference of fine-scale recombination rates using population genomic data Phil Trans R Soc B, December 27, 2008; 363(1512): 3921 - 3930. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Somogyi, B. Sipos, Z. Penzes, E. Kurucz, J. Zsamboki, D. Hultmark, and I. Ando Evolution of Genes and Repeats in the Nimrod Superfamily Mol. Biol. Evol., November 1, 2008; 25(11): 2337 - 2347. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 V. H. Pham, J.-J. Yong, S.-J. Park, D.-N. Yoon, W.-H. Chung, and S.-K. Rhee Molecular analysis of the diversity of the sulfide : quinone reductase (sqr) gene in sediment environments Microbiology, October 1, 2008; 154(10): 3112 - 3121. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Dohrmann, D. Janussen, J. Reitner, A. G. Collins, and G. Worheide Phylogeny and Evolution of Glass Sponges (Porifera, Hexactinellida) Syst Biol, June 1, 2008; 57(3): 388 - 405. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. W. Mount The Maximum Likelihood Approach for Phylogenetic Prediction CSH Protocols, April 1, 2008; 2008(5): pdb.top34 - pdb.top34. [Abstract] [Full Text]
|
|
|
|
 |
|
 G. P. Fournier and J. P. Gogarten Evolution of Acetoclastic Methanogenesis in Methanosarcina via Horizontal Gene Transfer from Cellulolytic Clostridia J. Bacteriol., February 1, 2008; 190(3): 1124 - 1127. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Jian, P. S. Soltis, M. A. Gitzendanner, M. J. Moore, R. Li, T. A. Hendry, Y.-L. Qiu, A. Dhingra, C. D. Bell, and D. E. Soltis Resolving an Ancient, Rapid Radiation in Saxifragales Syst Biol, February 1, 2008; 57(1): 38 - 57. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Lakner, P. van der Mark, J. P. Huelsenbeck, B. Larget, and F. Ronquist Efficiency of Markov Chain Monte Carlo Tree Proposals in Bayesian Phylogenetics Syst Biol, February 1, 2008; 57(1): 86 - 103. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Ekman, H. L. Andersen, and M. Wedin The Limitations of Ancestral State Reconstruction and the Evolution of the Ascus in the Lecanorales (Lichenized Ascomycota) Syst Biol, February 1, 2008; 57(1): 141 - 156. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. L Rabosky, S. C Donnellan, A. L Talaba, and I. J Lovette Exceptional among-lineage variation in diversification rates during the radiation of Australia's most diverse vertebrate clade Proc R Soc B, December 7, 2007; 274(1628): 2915 - 2923. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. S. McBride, J. R. Arguello, and B. C. O'Meara Five Drosophila Genomes Reveal Nonneutral Evolution and the Signature of Host Specialization in the Chemoreceptor Superfamily Genetics, November 1, 2007; 177(3): 1395 - 1416. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. A. McGuire, C. C. Witt, D. L. Altshuler, and J. V. Remsen Phylogenetic Systematics and Biogeography of Hummingbirds: Bayesian and Maximum Likelihood Analyses of Partitioned Data and Selection of an Appropriate Partitioning Strategy Syst Biol, October 1, 2007; 56(5): 837 - 856. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. I. Culley and G. F. Steward New Genera of RNA Viruses in Subtropical Seawater, Inferred from Polymerase Gene Sequences Appl. Envir. Microbiol., September 15, 2007; 73(18): 5937 - 5944. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. E. Wildman, M. Uddin, J. C. Opazo, G. Liu, V. Lefort, S. Guindon, O. Gascuel, L. I. Grossman, R. Romero, and M. Goodman Genomics, biogeography, and the diversification of placental mammals PNAS, September 4, 2007; 104(36): 14395 - 14400. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S.-Y. Cai, L. Xiong, C. G. Wray, N. Ballatori, and J. L. Boyer The farnesoid X receptor FXR{alpha}/NR1H4 acquired ligand specificity for bile salts late in vertebrate evolution Am J Physiol Regulatory Integrative Comp Physiol, September 1, 2007; 293(3): R1400 - R1409. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. C. Leman, M. K. Uyenoyama, M. Lavine, and Y. Chen The evolutionary forest algorithm Bioinformatics, August 1, 2007; 23(15): 1962 - 1968. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. B. Matheny, E. C. Vellinga, N. L. Bougher, O. Ceska, P.-A. Moreau, M. A. Neves, and J. F. Ammirati Taxonomy of displaced species of Tubaria Mycologia, July 1, 2007; 99(4): 569 - 585. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Liu and D. K. Pearl Species Trees from Gene Trees: Reconstructing Bayesian Posterior Distributions of a Species Phylogeny Using Estimated Gene Tree Distributions Syst Biol, June 1, 2007; 56(3): 504 - 514. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. B. Matheny, J. M. Curtis, V. Hofstetter, M. C. Aime, J.-M. Moncalvo, Z.-W. Ge, Z.-L. Yang, J. C. Slot, J. F. Ammirati, T. J. Baroni, et al. Major clades of Agaricales: a multilocus phylogenetic overview Mycologia, November 1, 2006; 98(6): 982 - 995. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Schoch, R. A. Shoemaker, K. A. Seifert, S. Hambleton, J. W. Spatafora, and P. W. Crous A multigene phylogeny of the Dothideomycetes using four nuclear loci Mycologia, November 1, 2006; 98(6): 1041 - 1052. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. I. Culley, A. S. Lang, and C. A. Suttle Metagenomic analysis of coastal RNA virus communities. Science, June 23, 2006; 312(5781): 1795 - 1798. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Lartillot and H. Philippe Computing Bayes Factors Using Thermodynamic Integration Syst Biol, April 1, 2006; 55(2): 195 - 207. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Rzhetsky, I. Iossifov, J. M. Loh, and K. P. White Microparadigms: Chains of collective reasoning in publications about molecular interactions PNAS, March 28, 2006; 103(13): 4940 - 4945. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. H Kozak, D. W Weisrock, and A. Larson Rapid lineage accumulation in a non-adaptive radiation: phylogenetic analysis of diversification rates in eastern North American woodland salamanders (Plethodontidae: Plethodon) Proc R Soc B, March 7, 2006; 273(1586): 539 - 546. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Scheffler and C. Seoighe A Bayesian Model Comparison Approach to Inferring Positive Selection Mol. Biol. Evol., December 1, 2005; 22(12): 2531 - 2540. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. W. Weisrock, L. J. Harmon, and A. Larson Resolving Deep Phylogenetic Relationships in Salamanders: Analyses of Mitochondrial and Nuclear Genomic Data Syst Biol, October 1, 2005; 54(5): 758 - 777. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Q. Minh, L. S. Vinh, A. von Haeseler, and H. A. Schmidt pIQPNNI: parallel reconstruction of large maximum likelihood phylogenies Bioinformatics, October 1, 2005; 21(19): 3794 - 3796. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. E. Berry, A. L. Hipp, K. J. Wurdack, B. Van Ee, and R. Riina Molecular phylogenetics of the giant genus Croton and tribe Crotoneae (Euphorbiaceae sensu stricto) using ITS and TRNL-TRNF DNA sequence data Am. J. Botany, September 1, 2005; 92(9): 1520 - 1534. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. K. Barker, A. Cibois, P. Schikler, J. Feinstein, and J. Cracraft Phylogeny and diversification of the largest avian radiation PNAS, July 27, 2004; 101(30): 11040 - 11045. [Abstract] [Full Text] [PDF]
|
|