An Improved Algorithm for Reducing the Solution Space of Sorting by Reversals

摘要

The goal of this paper is to give an efficient algorithm for sorting the genome with respect to other genome using reversal operation and to generate the optimum traces. Usually the number of solutions is large so solution space can be represented in compact manner by grouping equivalent solutions into traces. To reduce the memory requirement depth first approach is employed. Still there are some traces having reversals that are biologically not possible so it is of no use to further study them so such traces are discarded by applying some biological constraints at each step of the process for generating traces. This approach not only reduces memory and time consumption but also makes it easier to parallelize and a better evolutionary scenario of genomes is characterized. This allows us to efficiently handle large permutations so that the exploration time is visibly reduced.