Algorithms for a Restricted Genome Median Problem

• Helmuth O. M. Silva UFMS
• Diego P. Rubert UFMS
• Eloi Araujo UFMS
• Fábio V. Martinez UFMS

DOI: https://doi.org/10.5753/etc.2022.222734

Resumo

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.

Palavras-chave: Median problem, Comparative genomics, Computational biology

Referências

Bafna, V. and Pevzner, P. A. (1996). Genome rearrangements and sorting by reversals. SIAM J Comput, 25(2):272–289.

Bergeron, A., Mixtacki, J., and Stoye, J. (2006). A unifying view of genome rearrangements. In Proc. of WABI, volume 4175 of LNBI, pages 163–173.

Caprara, A. (2003). The reversal median problem. INFORMS J Comput, 15:93–113.

Feijão, P. and Meidanis, J. (2011). SCJ: A breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans Comput Biol Bioinf, 8(5):1318–1329.

Fertin, G., Labarre, A., Rusu, I., Tannier, E., and Vialette, S. (2009). Combinatorics of Genomes Rearrangements. The MIT Press.

Tannier, E., Zheng, C., and Sankoff, D. (2009). Multi-chromosomal median and halving problems under different genomic distances. BMC Bioinformatics, 10(120).

Yancopoulos, S., Attie, O., and Friedberg, R. (2005). Efficient sorting of genomic permutations by translocation, inversion and block interchanges. Bioinformatics, 21(16):3340–3346.