Algorithms for a Restricted Genome Median Problem - Silva, Helmuth O. M.; Rubert, Diego P.; Araujo, Eloi; Martinez, Fábio V. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.222734, 2022)
In the median problem we are given a set of three or more genomes and want to find a new genome minimizing the sum of pairwise distances between it and the given genomes. For almost all rearrangement operations the median problem is NP-hard. We study the median problem under a restricted rearrangement measure called c4-distance, which is closely related to breakpoint and DCJ distances. We propose two algorithms for its construction, one exact ILP-based and a combinatorial heuristic, and perform experiments on simulated data.