Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set SS of kk biologically related sequences and we are interested in a minimum cost evolutionary tree for SS. In many instances of this problem partial phylogenetic tree for SS is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows: Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set SS of kk related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of SS needs to satisfy, construct a minimum cost evolutionary tree for SS. In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k2−2/k.