Research On Algorithms For The Reciprocal Translocation Median Problem

Genome rearrnagements play an important role in the evolution of organism. A fundamental computational problem in the research of genome rearrangements is computing the minimum number of rearrangements necessary to transforms one genome into another. This is called the genomic distance problem. Reversals and translocations are common rearrangement events in the evolution of mammalian species. Reversals reverse the order and the direction of transcription of the genes in a segment inside a chromosome. Translocations exchange tails between two chromosomes. A translocation is reciprocal if none of the exchanged tails is empty. Generally, translocation is referred to reciprocal translocation. Much progress has been made in recent years on this problem. The formula for reversal distance between signed genome and the formula for reciprocal translocation distance between signed genome have been presented. The distance between genomes can reflects closely the evolutionary distance of the given organisms.The problem of reconstructing phylogenetic trees based on genome rearrnagements is of great interest in computational biology. In the context of genome rearrangements, a genome is usually represented as a permutation of (1,...,n), where each element represents a gene. Additionally, the strandedness of the genes is taken into account by giving each element an orientation. In the multiple genome rearrangement problem, one searches for a phylogenetic tree describing the most plausible rearrangement scenario for multiple genomes. Formally, given k genomes and a distance measure d, find a tree T with the k genomes as leaf nodes and assign ancestral genomes to internal nodes of T such that the tree is optimal with respect to d, i.e. the sum of rearrangement distances over all edges of the tree is minimal. If k=3, i.e. one searches for an ancestor such that the sum of the distances from this ancestor to three given genomes is minimized, namely the median problem. All of the actual algorithms for solving the multiple genome rearrangement problem rely on algorithms for solving the median problem. Unfortunately, this problem is NP-hard even for the simplest rearrangement measures, such as the reversal distance. Several effective algorithms have been developed for the reversal median problem, most of these algorithms need enumerating sorting reversals, which reduce the reversal distance between two genomes. Reversal median algorithms only work for unichromosomal genomes, but for multichromosomal genomes, reciprocal translocation is a common rearrangements event. When rearrangement measure be reciprocal translocation, the problem is reciprocal translocation median problem, which has no effective algorithms. Reciprocal translocation median problem is of some significance for analyses of the evolutionary relationship of multichromosomal genomes. Its complexity is still unknown, we guess that it is also NP hard. In this thesis, we derive two efficient algorithms to find a translocation median of three signed genomes. In the first stage, we derive a solution to the problem of finding all sorting translocations of one genome with respect to another; in the second stage, we develop an exact algorithm and a heuristic algorithm for translocations median problem, which mimic known algorithms for reversal median problem.