TARGETING - An efficient software package for solving the Maximal Pairing Problem on arbitrary trees
Publication
Arnold, C. and Stadler, PF. 2010. Polynomial algorithms for the Maximal Pairing Problem: efficient phylogenetic targeting on arbitrary trees.
Algorithms for Molecular Biology 5:25. (Link)
Description
Background
The Maximal Pairing Problem (MPP) is the prototype of a class of combinatorial optimization problems that are of considerable interest in bioinformatics: Given an arbitrary phylogenetic tree T and weights Ωxy for the paths between any two pairs of leaves (x, y), what is the collection of edge-disjoint paths between pairs of leaves that maximizes the total weight? Special cases of the MPP for binary trees and equal weights have been described previously. Algorithms to solve the general MPP are still missing, however.
Results
We describe a relatively simple dynamic programming algorithm for the special case of binary trees. The general case of multifurcating trees can then be treated by interleaving solutions to certain auxiliary Maximum Weighted Matching problems with an extension of this dynamic programming approach, resulting in an overall polynomial-time solution of complexity O(n4 log n) w.r.t. the number n of leaves. For binary trees, we furthermore discuss several constrained variants of the MPP as well as a partition function approach to the probabilistic version of the MPP.
Conclusions
The algorithms introduced here make it possible to solve the MPP also for large trees with high-degree vertices. This has practical relevance in the field of comparative phylogenetics and, for example, in the context of phylogenetic targeting, i.e., data collection with resource limitations.
Download
Current release: TARGETING Version 1.0 (April 2010, Sourcecode)
Installation Instructions
see Section Documentation below
Documentation
For more information, see the Documentation.