Approximation algorithms for constrained generalized tree alignment problem

Abstract: In generalized tree alignment problem, we are given a set of biologically related sequences and we are interested in a minimum cost evolutionary tree for . In many instances of this problem partial phylogenetic tree for 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 of related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of needs to satisfy, construct a minimum cost evolutionary tree for . 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 . [Copyright &y& Elsevier]