Preview

PDF 2Mb

The cophylogeny reconstruction problem is central in the inference of ancient relationships among ecologically linked groups of organisms. Although it is known to be NP-Complete, there have been several heuristics proposed that often find good solutions. One such approach is to fix the order of the internal nodes of the host phylogeny and use dynamic programming to recover an optimal reconstruction in polynomial time. A meta-heuristic framework is then leveraged to iterate over the factorial set of fixed node orderings. The original solution used a technique known as node mapping, taking and was designed to handle phylogenetic networks. There has since been a number of implementations for this problem which use specific properties of phylogenetic trees to reduce their running time. In this paper, we introduce a set of new optimisation techniques to achieve a running time improvement matching these cubic time algorithms, while using node mapping, and discuss how these newly proposed optimisation techniques may lead to an improvement in the generalised case of phylogenetic networks and provide valuable insights into how to construct an optimized algorithm for handling evolutionary systems with widespread parasites.

Item Type:	Refereed Article
Keywords:	cophylogeny, bioinformatics, dynamic programming, NP-Complete
Research Division:	Information and Computing Sciences
Research Group:	Theory of computation
Research Field:	Computational complexity and computability
Objective Division:	Expanding Knowledge
Objective Group:	Expanding knowledge
Objective Field:	Expanding knowledge in the biological sciences
UTAS Author:	Charleston, MA (Professor Michael Charleston)
ID Code:	100228
Year Published:	2014
Deposited By:	Mathematics and Physics
Deposited On:	2015-05-07
Last Modified:	2015-08-21
Downloads:	410 View Download Statistics