Format

Send to

Choose Destination
PeerJ. 2013 Jun 25;1:e89. doi: 10.7717/peerj.89. Print 2013.

PTree: pattern-based, stochastic search for maximum parsimony phylogenies.

Author information

1
Max-Planck Research Group for Computational Genomics and Epidemiology, Max-Planck Institute for Informatics , Saarbrücken , Germany.

Abstract

Phylogenetic reconstruction is vital to analyzing the evolutionary relationship of genes within and across populations of different species. Nowadays, with next generation sequencing technologies producing sets comprising thousands of sequences, robust identification of the tree topology, which is optimal according to standard criteria such as maximum parsimony, maximum likelihood or posterior probability, with phylogenetic inference methods is a computationally very demanding task. Here, we describe a stochastic search method for a maximum parsimony tree, implemented in a software package we named PTree. Our method is based on a new pattern-based technique that enables us to infer intermediate sequences efficiently where the incorporation of these sequences in the current tree topology yields a phylogenetic tree with a lower cost. Evaluation across multiple datasets showed that our method is comparable to the algorithms implemented in PAUP* or TNT, which are widely used by the bioinformatics community, in terms of topological accuracy and runtime. We show that our method can process large-scale datasets of 1,000-8,000 sequences. We believe that our novel pattern-based method enriches the current set of tools and methods for phylogenetic tree inference. The software is available under: http://algbio.cs.uni-duesseldorf.de/webapps/wa-download/.

KEYWORDS:

Local search; Maximum parsimony; Phylogeny reconstruction; Stochastic search

Supplemental Content

Full text links

Icon for PeerJ, Inc. Icon for PubMed Central
Loading ...
Support Center