Computer Engineering & Science >
An Algorithm of Reciprocal Translocationsfor Enumerating Signed Genomes
Received date: 2010-03-03
Revised date: 2010-06-14
Online published: 2010-09-02
During the past decades,several polynomial algorithms have been developed for the problem of sorting by reciprocal translocations (abbreviated as SRT), which is to find the shortest sequence of reciprocal translocations that transforms one genome into another. However, there are many shortest sequences of reciprocal translocations for most problem instances. In consequence, the problem of finding all the shortest sequences of reciprocal translocations is a natural generalization of SRT. This problem reduces easily to the problem of finding all the “sorting reciprocal translocations” of one genome with respect to another—that is, all translocations ρ which can reduce the translocation distance of the resulting genome from another after applying ρ on one genome. In this paper, we give an efficient algorithm for finding all the sorting reciprocal translocations. While the new algorithm improves little in asymptotic time complexity, the experimental results show that it performs better in practice than the brute force method.
CHEN Chao,LUAN Junfeng . An Algorithm of Reciprocal Translocationsfor Enumerating Signed Genomes[J]. Computer Engineering & Science, 2010 , 32(9) : 152 -156 . DOI: 10.3969/j.issn.1007130X.2010.
/
| 〈 |
|
〉 |