Academic Journals Database
Disseminating quality controlled scientific knowledge

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

Author(s): Ivan Gregor | Lars Steinbrück | Alice C. McHardy

Journal: PeerJ
ISSN 2167-8359

Volume: 1;
Start page: e89;
Date: 2013;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Phylogeny reconstruction | Maximum parsimony | Local search | Stochastic search

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:
Save time & money - Smart Internet Solutions     

Tango Jona
Tangokurs Rapperswil-Jona