pplacer: linear time maximum-likelihood and Bayesian phylogenetic placement of sequences onto a fixed reference tree
Tóm tắt
Likelihood-based phylogenetic inference is generally considered to be the most reliable classification method for unknown sequences. However, traditional likelihood-based phylogenetic methods cannot be applied to large volumes of short reads from next-generation sequencing due to computational complexity issues and lack of phylogenetic signal. "Phylogenetic placement," where a reference tree is fixed and the unknown query sequences are placed onto the tree via a reference alignment, is a way to bring the inferential power offered by likelihood-based approaches to large data sets. This paper introduces pplacer, a software package for phylogenetic placement and subsequent visualization. The algorithm can place twenty thousand short reads on a reference tree of one thousand taxa per hour per processor, has essentially linear time and memory complexity in the number of reference taxa, and is easy to run in parallel. Pplacer features calculation of the posterior probability of a placement on an edge, which is a statistically rigorous way of quantifying uncertainty on an edge-by-edge basis. It also can inform the user of the positional uncertainty for query sequences by calculating expected distance between placement locations, which is crucial in the estimation of uncertainty with a well-sampled reference tree. The software provides visualizations using branch thickness and color to represent number of placements and their uncertainty. A simulation study using reads generated from 631 COG alignments shows a high level of accuracy for phylogenetic placement over a wide range of alignment diversity, and the power of edge uncertainty estimates to measure placement confidence. Pplacer enables efficient phylogenetic placement and subsequent visualization, making likelihood-based phylogenetics methodology practical for large collections of reads; it is freely available as source code, binaries, and a web service.
Tài liệu tham khảo
Margulies M, Egholm M, Altman W, Attiya S, Bader J, Bemben L, Berka J, Braverman M, Chen Y, Chen Z, et al.: Genome sequencing in microfabricated high-density picolitre reactors. Nature 2005, 437: 376–380.
Culley A, Lang A, Suttle C: Metagenomic analysis of coastal RNA virus communities. Science 2006, 312(5781):1795–1798. 10.1126/science.1127404
Gill S, Pop M, DeBoy R, Eckburg P, Turnbaugh P, Samuel B, Gordon J, Relman D, Fraser-Liggett C, Nelson K: Metagenomic analysis of the human distal gut microbiome. Science 2006, 312(5778):1355–1359. 10.1126/science.1124234
Venter J, Remington K, Heidelberg J, Halpern A, Rusch D, Eisen J, Wu D, Paulsen I, Nelson K, Nelson W, et al.: Environmental genome shotgun sequencing of the Sargasso Sea. Science 2004, 304(5667):66–74. 10.1126/science.1093857
Tringe S, Rubin E: Metagenomics: DNA sequencing of environmental samples. Nat Rev Genet 2005, 6(11):805–814. 10.1038/nrg1709
Martín H, Ivanova N, Kunin V, Warnecke F, Barry K, McHardy A, Yeates C, He S, Salamov A, Szeto E, et al.: Metagenomic analysis of two enhanced biological phosphorus removal (EBPR) sludge communities. Nat Biotech 2006, 24: 1263–1269. 10.1038/nbt1247
Warnecke F, Luginbühl P, Ivanova N, Ghassemian M, Richardson T, Stege J, Cayouette M, McHardy A, Djord-jevic G, Aboushadi N, et al.: Metagenomic and functional analysis of hindgut microbiota of a wood-feeding higher termite. Nature 2007, 450(7169):560–565. 10.1038/nature06269
Baker B, Banfield J: Microbial communities in acid mine drainage. FEMS Microbiol Ecol 2003, 44(2):139–152. 10.1016/S0168-6496(03)00028-X
Altschul S, Gish W, Miller W, Myers E, Lipman D: Basic local alignment search tool. J Mol Biol 1990, 215(3):403–410.
Huson D, Auch A, Qi J, Schuster S: MEGAN analysis of metagenomic data. Genome Res 2007, 17(3):377. 10.1101/gr.5969107
McHardy A, Martín H, Tsirigos A, Hugenholtz P, Rigoutsos I: Accurate phylogenetic classification of variable-length DNA fragments. Nature Methods 2007, 4: 63–72. 10.1038/nmeth976
Diaz N, Krause L, Goesmann A, Niehaus K, Nattkemper T: TACOA-Taxonomic classification of environmental genomic fragments using a kernelized nearest neighbor approach. BMC Bioinfo 2009, 10: 56. 10.1186/1471-2105-10-56
Brady A, Salzberg S: Phymm and PhymmBL: metagenomic phylogenetic classification with interpolated Markov models. Nature Methods 2009, 6(9):673–676. 10.1038/nmeth.1358
Allman E, Rhodes J: The identifability of tree topology for phylogenetic models, including covarion and mixture models. J Comput Biol 2006, 13(5):1101–1113. 10.1089/cmb.2006.13.1101
Allman E, Rhodes J: Identifying evolutionary trees and substitution parameters for the general Markov model with invariable sites. Math Biosci 2008, 211: 18–33. 10.1016/j.mbs.2007.09.001
Shimodaira H, Hasegawa M: Multiple comparisons of log-likelihoods with applications to phylogenetic inference. Mol Biol Evol 1999, 16: 1114–1116.
Yang Z: Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites: approximate methods. J Mol Evol 1994, 39(3):306–314. 10.1007/BF00160154
Le S, Gascuel O: An improved general amino acid replacement matrix. Mol Biol Evol 2008, 25(7):1307. 10.1093/molbev/msn067
Felsenstein J: Inferring Phylogenies. 2004.
Chor B, Tuller T: Finding a maximum likelihood tree is hard. J ACM 2006, 53(5):744. 10.1145/1183907.1183909
Roch S: A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE/ACM TCBB 2006, 92–94.
Guindon S, Gascuel O: A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Sys Biol 2003, 696–704. 10.1080/10635150390235520
Stamatakis A: RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 2006, 22(21):2688. 10.1093/bioinformatics/btl446
Zwickl D: Genetic algorithm approaches for the phylogenetic analysis of large biological sequence datasets under the maximum likelihood criterion. PhD thesis. The University of Texas at Austin; 2006.
Price MN, Dehal PS, Arkin AP: FastTree 2: Approximately Maximum-Likelihood Trees for Large Alignments. PLoS ONE 2010, 5(3):e9490. 10.1371/journal.pone.0009490
Steel M, Székely L: Inverting random functions II: Explicit bounds for discrete maximum likelihood estimation, with applications. SIAM J Discrete Math 2002, 15(4):562–578. 10.1137/S089548010138790X
Moret B, Roshan U, Warnow T: Sequence-length requirements for phylogenetic methods. Lecture Notes in Computer Science 2002, 343–356. full_text
Berger S, Stamatakis A: Evolutionary Placement of Short Sequence Reads. Submitted to Sys Biol 2009. [http://arxiv.org/abs/0911.2852]
Margulies M, Egholm M, Altman W, Attiya S, Bader J, Bemben L, Berka J, Braverman M, Chen Y, Chen Z, et al.: Genome sequencing in open microfabricated high density picoliter reactors. Nature 2005, 437(7057):376.
Mardis E: Next-generation DNA sequencing methods. Ann Rev Genomics Human Genet 2008, 9: 387. 10.1146/annurev.genom.9.081307.164359
Lemmon A, Brown J, Stanger-Hall K, Lemmon E: The Effect of Ambiguous Data on Phylogenetic Estimates Obtained by Maximum Likelihood and Bayesian Inference. Syst Biol 2009, 58: 130. 10.1093/sysbio/syp017
Archaeopteryx[http://www.phylosoft.org/archaeopteryx/]
Dendroscope[http://www-ab.informatik.uni-tuebingen.de/software/dendroscope]
Mooers A, Heard S: Evolutionary process from phylogenetic tree shape. Q Rev Biol 1997, 72: 31–54. 10.1086/419657
Lozupone C, Knight R: UniFrac: a new phylogenetic method for comparing microbial communities. Appl Enviro Microbiol 2005, 71(12):8228. 10.1128/AEM.71.12.8228-8235.2005
Kluge A, Farris J: Quantitative phyletics and the evolution of anurans. Syst Zool 1969, 1–32. 10.2307/2412407
Felsenstein J: Evolutionary trees from DNA sequences: a maximum likelihood approach. J Mol Evol 1981, 17(6):368–376. 10.1007/BF01734359
Monier A, Claverie J, Ogata H: Taxonomic distribution of large DNA viruses in the sea. Genome Biol 2008, 9(7):R106. 10.1186/gb-2008-9-7-r106
Von Mering C, Hugenholtz P, Raes J, Tringe S, Doerks T, Jensen L, Ward N, Bork P: Quantitative phylogenetic assessment of microbial communities in diverse environments. Science 2007, 315(5815):1126. 10.1126/science.1133420
Kosakovsky P, Posada D, Stawiski E, Chappey C, Poon A, Hughes G, Fearnhill E, Gravenor M, Leigh B, Frost S: An evolutionary model-based algorithm for accurate phylogenetic breakpoint mapping and subtype prediction in HIV-1. PLoS Comp Biol 2009, 5(11):e1000581. 10.1371/journal.pcbi.1000581
Zwickl D, Hillis D: Increased taxon sampling greatly reduces phylogenetic error. Sys Biol 2002, 51(4):588. 10.1080/10635150290102339
Cueto M, Matsen F: The polyhedral geometry of phylogenetic rogue taxa. In press Bull Math Biol 2010. [http://arxiv.org/abs/1001.5241]
Munch K, Boomsma W, Willerslev E, Nielsen R: Fast phylogenetic DNA barcoding. Phil Trans Royal Soc B 2008, 363(1512):3997–4002. 10.1098/rstb.2008.0169
Drummond A, Rambaut A: BEAST v1.0.2003. [http://beast.bio.ed.ac.uk/]
Huelsenbeck JP, Ronquist F: MRBAYES: Bayesian inference of phylogeny. Bioinformatics 2001, 17: 754–755. 10.1093/bioinformatics/17.8.754
Whelan S, Goldman N: A general empirical model of protein evolution derived from multiple protein families using a maximum-likelihood approach. Mol Biol Evol 2001, 18(5):691–699.
Objective Caml[http://caml.inria.fr/ocaml/index.en.html]
The GNU scientific library[http://www.gnu.org/software/gsl/]
Han M, Zmasek C: phyloXML: XML for evolutionary biology and comparative genomics. BMC Bioinfo 2009, 10: 356. 10.1186/1471-2105-10-356
Zurawski G, Bohnert H, Whitfeld P, Bottomley W: Nucleotide sequence of the gene for the Mr 32,000 thylakoid membrane protein from Spinacia oleracea and Nicotiana debneyi predicts a totally con-served primary translation product of Mr 38,950. Proc Nat Acad Sci 1982, 79(24):7699–7703. 10.1073/pnas.79.24.7699
Zeidner G, Preston C, Delong E, Massana R, Post A, Scanlan D, Beja O: Molecular diversity among marine picophytoplankton as revealed by psbA analyses. Environ Microbiol 2003, 5(3):212. 10.1046/j.1462-2920.2003.00403.x
Sullivan M, Lindell D, Lee J, Thompson L, Bielawski J, Chisholm S: Prevalence and evolution of core photosystem II genes in marine cyanobacterial viruses and their hosts. PLoS Biol 2006, 4(8):e234. 10.1371/journal.pbio.0040234
Millard A, Clokie M, Shub D, Mann N: Genetic organization of the psbAD region in phages infecting marine Synechococcus strains. PNAS 2004, 101(30):11007. 10.1073/pnas.0401478101
Lindell D, Jaffe J, Coleman M, Futschik M, Axmann I, Rector T, Kettler G, Sullivan M, Steen R, Hess W, et al.: Genome-wide expression dynamics of a marine virus and host reveal features of co-evolution. Nature 2007, 449(7158):83–86. 10.1038/nature06130
Chenard C, Suttle C: Phylogenetic diversity of sequences of cyanophage photosynthetic gene psbA in marine and freshwaters. Appl Enviro Microbiol 2008, 74(17):5317. 10.1128/AEM.02480-07
Williamson S, Rusch D, Yooseph S, Halpern A, Heidelberg K, Glass J, Andrews-Pfannkoch C, Fadrosh D, Miller C, Sutton G, et al.: The Sorcerer II Global Ocean Sampling Expedition: metagenomic characterization of viruses within aquatic microbial samples. PLoS ONE 2008, 3(1):e1456. 10.1371/journal.pone.0001456
Sharon I, Tzahor S, Williamson S, Shmoish M, Man-Aharonovich D, Rusch D, Yooseph S, Zeidner G, Golden S, Mackey S, et al.: Viral photosynthetic reaction center genes and transcripts in the marine environment. The ISME Journal 2007, 1(6):492–501. 10.1038/ismej.2007.67
Eddy S: Profile hidden Markov models. Bioinformatics 1998, 14(9):755–763. 10.1093/bioinformatics/14.9.755
Tatusov R, Galperin M, Natale D, Koonin E: The COG database: a tool for genome-scale analysis of protein functions and evolution. Nucleic Acids Res 2000, 28: 33. 10.1093/nar/28.1.33
Stark M, Berger S, Stamatakis A, von Mering C: MLTreeMap- accurate Maximum Likelihood placement of environmental DNA sequences into taxonomic and functional reference phylogenies. BMC Genomics 2010, 11: 461. 10.1186/1471-2164-11-461
Krause L, Diaz N, Goesmann A, Kelley S, Nattkemper T, Rohwer F, Edwards R, Stoye J: Phylogenetic classification of short environmental DNA fragments. Nucleic Acids Res 2008.
Munch K, Boomsma W, Huelsenbeck J, Willerslev E, Nielsen R: Statistical Assignment of DNA Sequences Using Bayesian Phylogenetics. Sys Biol 2008, 57(5):750–757. 10.1080/10635150802422316
Felsenstein J: PHYLIP (Phylogeny Inference Package) version 3.6. In Distributed by the author. Department of Genome Sciences, University of Washington, Seattle; 2004.
Schmidt H, Strimmer K, Vingron M, von Haeseler A: TREE-PUZZLE: maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics 2002, 18(3):502–504. 10.1093/bioinformatics/18.3.502
Kishino H, Miyata T, Hasegawa M: Maximum likelihood inference of protein phylogeny and the origin of chloroplasts. J Mol Evol 1990, 31(2):151–160. 10.1007/BF02109483
Strimmer K, Rambaut A: Inferring confidence sets of possibly misspecified gene trees. Proc Royal Soc B 2002, 269(1487):137–142. 10.1098/rspb.2001.1862
Wu M, Eisen J: A simple, fast, and accurate method of phylogenomic inference. Genome Biol 2008, 9(10):R151. 10.1186/gb-2008-9-10-r151
Stamatakis A, Komornik Z, Berger S: Evolutionary placement of short sequence reads on multi-core architectures. Proceedings of AICCSA-10, at 8th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA-10), Hammamet, Tunisia 2010.
Evans S, Matsen F: The phylogenetic Kantorovich-Rubinstein metric for environmental sequence samples. submitted to JRSS B 2010. [http://arxiv.org/abs/1005.1699v2]
Lozupone C, Hamady M, Kelley S, Knight R: Quantitative and qualitative {beta} diversity measures lead to different insights into factors that structure microbial communities. Appl Environ Microbiol 2007, 73(5):1576. 10.1128/AEM.01996-06
Pplacer Github repository[http://github.com/matsen/pplacer]
Turnbaugh P, Hamady M, Yatsunenko T, Cantarel B, Duncan A, Ley R, Sogin M, Jones W, Roe B, Affourtit J, et al.: A core gut microbiome in obese and lean twins. Nature 2008, 457(7228):480–484. 10.1038/nature07540
CAMERA - Community Cyberinfrastructure for Advanced Marine Microbial Ecology Research and Analysis[http://camera.calit2.net/]
Drummond A, Ashton B, Cheung M, et al.: Geneious Version 3.5. 2007.
FigTree[http://tree.bio.ed.ac.uk/software/gtree/]
Stamatakis A: Phylogenetic models of rate heterogeneity: a high performance computing perspective. Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International 2006, 8.