Breakpoint Distance and PQ-Trees

摘要: The PQ-tree is a fundamental data structure that can encode large sets of permutations. It has recently been used in comparative genomics to model ancestral genomes with some uncertainty: given phylogeny for species, extant are represented by permutations on the leaves tree, and each internal node phylogenetic tree represents an extinct genome, PQ-tree. An open problem related this approach then quantify evolution between PQ-trees. In paper we present results two problems comparison motivated application. First, show comparing PQ-trees computing minimum breakpoint distance among all pairs generated respectively considered NP-complete unsigned Next, consider generalization classical Breakpoint Median problem, where genome p given, ≥ 1, want compute permutation minimizes sum distances We Fixed-Parameter Tractable respect value. This last result applies both signed permutations, uni-chromosomal multi-chromosomal