FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix Export

@article{citeulike:4466193, abstract = {Gene families are growing rapidly, but standard methods for inferring phylogenies do not scale to alignments with over 10,000 sequences. We present FastTree, a method for constructing large phylogenies and for estimating their reliability. Instead of storing a distance matrix, FastTree stores sequence profiles of internal nodes in the tree. FastTree uses these profiles to implement Neighbor-Joining and uses heuristics to quickly identify candidate joins. FastTree then uses nearest neighbor interchanges to reduce the length of the tree. For an alignment with N sequences, L sites, and a different characters, a distance matrix requires O(N2) space and O(N2L) time, but FastTree requires just O(NLa + N[IMG]/medium/molbiolevolmsp077fx9\_ht.gif" ALT="Formula ">) memory and O(N[IMG]/medium/molbiolevolmsp077fx9\_ht.gif" ALT="Formula ">log (N)La) time. To estimate the tree's reliability, FastTree uses local bootstrapping, which gives another 100-fold speedup over a distance matrix. For example, FastTree computed a tree and support values for 158,022 distinct 16S ribosomal RNAs in 17 h and 2.4 GB of memory. Just computing pairwise Jukes-Cantor distances and storing them, without inferring a tree or bootstrapping, would require 17 h and 50 GB of memory. In simulations, FastTree was slightly more accurate than Neighbor-Joining, BIONJ, or FastME; on genuine alignments, FastTree's topologies had higher likelihoods. FastTree is available at http://microbesonline.org/fasttree. 10.1093/molbev/msp077}, author = {Price, Morgan N. and Dehal, Paramvir S. and Arkin, Adam P.}, citeulike-article-id = {4466193}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/molbev/msp077}, citeulike-linkout-1 = {http://mbe.oxfordjournals.org/content/26/7/1641.abstract}, citeulike-linkout-2 = {http://mbe.oxfordjournals.org/content/26/7/1641.full.pdf}, citeulike-linkout-3 = {http://mbe.oxfordjournals.org/cgi/content/abstract/26/7/1641?etoc}, citeulike-linkout-4 = {http://view.ncbi.nlm.nih.gov/pubmed/19377059}, citeulike-linkout-5 = {http://www.hubmed.org/display.cgi?uids=19377059}, day = {1}, doi = {10.1093/molbev/msp077}, journal = {Mol Biol Evol}, keywords = {alignment, evolution, software}, month = {July}, number = {7}, pages = {1641--1650}, posted-at = {2009-10-28 09:51:36}, priority = {2}, title = {FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix}, url = {http://dx.doi.org/10.1093/molbev/msp077}, volume = {26}, year = {2009} }

TY - JOUR ID - citeulike:4466193 L3 - citeulike-article-id:4466193 N2 - Gene families are growing rapidly, but standard methods for inferring phylogenies do not scale to alignments with over 10,000 sequences. We present FastTree, a method for constructing large phylogenies and for estimating their reliability. Instead of storing a distance matrix, FastTree stores sequence profiles of internal nodes in the tree. FastTree uses these profiles to implement Neighbor-Joining and uses heuristics to quickly identify candidate joins. FastTree then uses nearest neighbor interchanges to reduce the length of the tree. For an alignment with N sequences, L sites, and a different characters, a distance matrix requires O(N2) space and O(N2L) time, but FastTree requires just O(NLa + N[IMG]/medium/molbiolevolmsp077fx9_ht.gif" ALT="Formula ">) memory and O(N[IMG]/medium/molbiolevolmsp077fx9_ht.gif" ALT="Formula ">log (N)La) time. To estimate the tree's reliability, FastTree uses local bootstrapping, which gives another 100-fold speedup over a distance matrix. For example, FastTree computed a tree and support values for 158,022 distinct 16S ribosomal RNAs in 17 h and 2.4 GB of memory. Just computing pairwise Jukes-Cantor distances and storing them, without inferring a tree or bootstrapping, would require 17 h and 50 GB of memory. In simulations, FastTree was slightly more accurate than Neighbor-Joining, BIONJ, or FastME; on genuine alignments, FastTree's topologies had higher likelihoods. FastTree is available at http://microbesonline.org/fasttree. 10.1093/molbev/msp077 IS - 7 JF - Mol Biol Evol EP - 1650 TI - FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix VL - 26 SP - 1641 KW - alignment KW - evolution KW - software AU - Price, Morgan AU - Dehal, Paramvir AU - Arkin, Adam PY - 2009/07/01/ UR - http://dx.doi.org/10.1093/molbev/msp077 ER -