On the complexity and approximation of syntenic distance

摘要: Abstract The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau Sankoff. Here, chromosome is represented as set of genes genome collections chromosomes. syntenic two defined minimum number translocations, fusions fissions required to transform one into other. We prove that computing NP-hard give simple algorithm with performance ratio 2. For case when an upper bound d on known, we show optimal sequence can be found in O(nk + 2o(d2)) time, where n k are chromosomes given genomes. Next, if operations transforming significantly restricted, nevertheless find solution performs at most O(log d) additional moves, moves performed unrestricted optimum. This result should help design algorithms. Finally, investigate median problem: Given three genomes, construct minimizing total compute corresponding distance. problem has application inference phytogenies based polynomial time 4+e any constant e > 0.