HMC CS Technical Report CS-2011-1: Faster Dynamic Programming Algorithms for the Cophylogeny Reconstruction Problem
Anak Yodpinyanee, Benjamin Cousins, John Peebles, Tselil Schramm, Ran Libeskind-Hadas · 2011
The cophylogeny reconstruction problem is fundamental in the study of coevolution. Although the problem is known to be NP-complete (LibeskindHadas & Charleston 2009, Ovadia, Fielder, Conow & Libeskind-Hadas 2011), several software tools have been developed that solve small instances optimally (e.g. TreeMap) or use heuristics to eciently nd good, but not necessarily optimal, solutions (e.g. TreeFitter, Tarzan, Jane, CoRe-PA). The latter approaches generally use dynamic programming (DP) algorithms that, while not identical, are fundamentally similar. In this paper we describe a new general \edge-based dynamic programming approach that is substantially more ecient than existing approaches. The new edge-based approach can be used in lieu of the DP steps in existing systems, improving running time and obtaining equally good solutions. For example, the O(n 3 ) DP in the CoRe-PA system can be replaced by a O(n 2 ) edge-based DP and the O(n 7 ) DP step in the Jane 1 cophylogeny tool has been replaced by O(n 3 ) \edge-based DP in Jane 2 (Jane n.d.), where n is the number of nodes in each tree.