Approximation algorithms for constrained generalized tree alignment problem ?
In generalized tree alignment problem, we are given a set S S of k k biologically related sequences and we are interested in a minimum cost evolutionary tree for S S . In many instances of this problem partial phylogenetic tree for S S 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 S S of k k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S S needs to satisfy, construct a minimum cost evolutionary tree for S S .
approximation algorithms generalized tree alignment analysis of algorithms bioinformatics computational biology