Affordable Access

deepdyve-link
Publisher Website

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

Authors
  • Gregor, Ivan1
  • Steinbrück, Lars
  • McHardy, Alice C
  • 1 Max-Planck Research Group for Computational Genomics and Epidemiology, Max-Planck Institute for Informatics , Saarbrücken , Germany. , (Germany)
Type
Published Article
Journal
PeerJ
Publisher
PeerJ
Publication Date
Jan 01, 2013
Volume
1
Identifiers
DOI: 10.7717/peerj.89
PMID: 23825794
Source
Medline
Keywords
Language
English
License
Unknown

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/.

Report this publication

Statistics

Seen <100 times