期刊名称：International Journal of Computer Technology and Applications
电子版ISSN：2229-6093
出版年度：2011
卷号：2
期号：3
页码：579-589
出版社：Technopark Publications
摘要：The arrangement distance between single chromosomegenomes can be estimated as the minimumnumber of inversions required to transform the geneordering observed in one into that observed in theother. This measure, known as “inversion distance,”can be computed as the reversal distance betweensigned permutations. During the past decade, muchprogress has been made both on the problem ofcomputing reversal distance and on the relatedproblem of finding a minimum-length sequence of reversals, which is known as “sorting by reversals.” Incomparative genomics, algorithms that sortpermutations by reversals are often used to propose evolutionary scenarios of large-scale genomicmutations between species. One of the main problems of such methods is that they give one solution while the number of optimal solutions is huge, with no criteria todiscriminate among them. Bergeron et al. started to give some structure to the set of optimal solutions, inorder to be able to deliver more presentable resultsthan only one solution or a complete list of all solutions. This paper presents parallel algorithms to enumerate total sorting sequence of two signed permutations. These algorithms are based on Hannenhalli and Pevzner’s theory and composed offour key steps: Construct break point graph, computethe optimal distance, find the possible next reversalsequence and finally enumerate the total possiblesorting sequences
