• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊
论文

An Algorithm of Reciprocal Translocationsfor Enumerating  Signed Genomes

Expand
  • (School of Computer Science and Technology,Shandong University,Jinan 250101,China)

Received date: 2010-03-03

  Revised date: 2010-06-14

  Online published: 2010-09-02

Abstract

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.

Cite this article

CHEN Chao,LUAN Junfeng . An Algorithm of Reciprocal Translocationsfor Enumerating  Signed Genomes[J]. Computer Engineering & Science, 2010 , 32(9) : 152 -156 . DOI: 10.3969/j.issn.1007130X.2010.

Outlines

/