Multiple duplicated gene rearrangement algorithm for arbitrary target

Abstract

The genome rearrangement can be used as a measurement of evolutionary distance between two organisms using the gene order of genomic data. The ultimate goal of genome rearrangement studies is finding a series of rearrangement scenarios to transform one genome into another by using the minimum number of the rearrangement events such as reversal, transposition and transversal. Hannenhalli and Pevzner introduced the notion of breakpoint graph to compute the reversal distance. Their algorithm determines the minimum number of reversals required for rearranging a genome to another -- but only in the absence of gene duplicates. However, duplicates often account for 40% of a genome. Therefore, the idea of breakpoint graph is clearly unsuitable for computing the reversal distances for multi-gene families. In this dissertation, we show how to extend Hannenhalli and Pevzner's approach to deal with genomes with multi-gene families. We propose a new heuristic algorithm to compute the reversal distances between two genomes with multi-gene families via binary integer programming. Then, we will be applied for the others two rearrangement distance (transposition and transversal). The experimental results on both synthetic and real biological data demonstrate that the proposed algorithm is able to find the reversal distance with high accuracy.