Multi-Break Rearrangements and Breakpoint Re-Uses: From Circular to Linear Genomes

Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While 2-break rearrangements represent standard reversals, fusions, fissions, and translocations, 3-break rearrangements represent a natural general-ization of transpositions. Alekseyev and Pevzner (2007a, 2008a) studied multi-break rear-rangements in circular genomes and further applied them to the analysis of chromosomal evolution in mammalian genomes. In this paper, we extend these results to the more difficult case of linear genomes. In particular, we give lower bounds for the rearrangement distance between linear genomes and for the breakpoint re-use rate as functions of the number and proportion of transpositions. We further use these results to analyze comparative genomic architecture of mammalian genomes. Key words: algorithms, combinatorics, computational molecular biology, evolution, genomic rearrangements