標題: Sorting by Reversals, Generalized Transpositions, and Translocations Using Permutation Groups
作者: Huang, Yen-Lin
Lu, Chin Lung
生物資訊及系統生物研究所
Institude of Bioinformatics and Systems Biology
關鍵字: algebra;block-interchange;fission;fusion;generalized transposition;genome rearrangement;permutation group;reversal;translocation
公開日期: 1-五月-2010
摘要: In this article, we consider the problem of sorting a linear/circular, multi-chromosomal genome by reversals, block-interchanges (i.e., generalized transpositions), and translocations (including fusions and fissions) where the used operations can be weighted differently, which aims to find a sequence of reversal, block-interchange, and translocation operations such that the sum of these operation weights in the sequence is minimum. It is known that this sorting problem can be solved in polynomial time on the basis of breakpoint graphs, when block-interchanges are weighted 2 (or >= 3) and the others are weighted 1. In this study, we design a novel and easily implemented algorithm for this problem by utilizing the permutation group theory in algebra.
URI: http://dx.doi.org/10.1089/cmb.2009.0025
http://hdl.handle.net/11536/5470
ISSN: 1066-5277
DOI: 10.1089/cmb.2009.0025
期刊: JOURNAL OF COMPUTATIONAL BIOLOGY
Volume: 17
Issue: 5
起始頁: 685
結束頁: 705
顯示於類別:期刊論文


文件中的檔案:

  1. 000279272400003.pdf