Sorting Algorithm To The Shift Of The Genome

With the development of fast sequencing techniques, large-scale DNA molecules are investigated with respect to the relative order of genes in them. The sorting of genomes rearrangements becomes an important research area of computational biology and bioinformatics. Many research results show that genome rearrangement is a common mode for biological evolution and one main reason for the diversities of plants, mammals and bacteria.There are three classical genomes rearrangements operations: Reversal, Translocation and Transposition. A rearrangement operation transforms one genome into another genome. Reversal and transposition operations always act on one chromosome, while a translocation operation acts on two chromosomes. Given two genomes, the problem of rearrangements sorting is to compute a shortest sequence of rearrangements operations that transforms one genome into another. Based on many tests data accumulated by molecular biology, this shortest sequence is viewed as a better estimation of the affinity relations among species, and it is helpful to guess the real biological evolution process.A genome is a set of chromosomes and a chromosome is a sequence of genes. Each gene is represented by an integer. A gene has a direction. When the direction of every gene in a signed genome is known, we use a signed integer to indicate the direction. When the directions of genes in an unsigned genome are unknown, we use unsigned integers to represent the genes. For the problem of sorting signed genomes, a sorting operation can change both the gene sequence and the signs of genes. For the problem of sorting unsigned genomes, a sorting operation can only change the gene sequence, and can not change a sign of a gene.For the problem of sorting signed genomes by translocations, Hannenhalli designed the first O(n~3) polynomial-time exact algorithm and gave the formula to compute the translocation distance of signed genomes. Lately, Zhu and Ma improved the time complexity of this algorithm into O(n~2logn), and Wang etc improved it into O(n~2). The problem of sorting unsigned genomes by translocations has been proved a NP-hard problem. Kececioglu and Ravi gave a ratio-2 approximation algorithm for the...