Abstract
Recent advances in sequencing technologies revealed the ubiquity of genome rearrangements between each and every one of us. These large scale mutationsrearrange segments of chromosomes and have a profound impact on genetic variation, disease, and evolution. The study of the consequences of rearrangements along with their molecular mechanisms, however, is still in its infancy.Given extant genomes, we are interested in tracing back the evolutionary rearrangement scenarios that transformed their least common ancestor into the genomes that we observe today. This helps not only to reveal evolutionary relationships between organisms, but also provides a window for the study of genome rearrangements themselves.The central computational problem in this subfield of comparative genomicsis that of finding optimal rearrangement scenarios transforming one genome into another. Historically all rearrangements were treated as being equally possible, and optimal scenarios were those that contained the minimum number of rearrangements. Recent advances in biology, however, allow us to devise much more sophisticated models. We present a short survey of the existingwork on using biological constraints for genome rearrangements, and argue that a much more flexible approach is necessary to accompany the influx of newly available biological data.In this work we propose an extremely general framework for genome rearrangements with biological constraints. Our main contribution is a polynomial time algorithm that, for an arbitrary cost function, finds a minimum cost scenario among those of minimum length. Along the way we establish a number of novel links between sorting genomes with double cut and join rearrangements, sorting graphs with 2-breaks or edge swaps, sorting permutations with mathematical transpositions, sorting strings with interchanges, and token swapping on graphs.