Signed Rearrangement Distances Considering Repeated Genes and Intergenic Regions

Genome Rearrangement distance problems are used to infer the evolutionary distance between genomes. These problems look at the number of mutations called rearrangement events necessary to transform one genome into another. Two commonly studied rearrange- ments are the reversal, which inverts a sequence of genes, and the transposition, which exchanges two consecutive sequences of genes. Seminal works on that topic looked only at the sequence of genes and assumed that no gene has more than one copy. More realistic models have been assuming multiple copies of a gene or have been taking the number of nucleotides between intergenic regions into account. This work combines these two generalizations defining the Signed Intergenic Reversal Distance (SIRD) and the Signed Intergenic Reversal and Transposition Distance (SIRTD) problems. Using a relationship with a problem called Signed Minimum Common Intergenic String Partition, we show Θ(k)-approximation algorithms for the SIRD and the SIRTD problems, where k is the maximum number of copies of a gene in the genomes. Our experimental tests on simulated genomes show that the algorithms tend to find low distances despite the high theorical approximation factor.