標題: An improved algorithm for sorting by block-interchanges based on permutation groups
作者: Huang, Yen-Lin
Huang, Cheng-Chen
Tang, Chuan Yi
Lu, Chin Lung
生物科技學系
生物資訊及系統生物研究所
Department of Biological Science and Technology
Institude of Bioinformatics and Systems Biology
關鍵字: Algorithm;Data structure;Genome rearrangement;Permutation group;Block-interchange;Generalized transposition;Permutation tree
公開日期: 1-四月-2010
摘要: Given a chromosome represented by a permutation of genes, a block-interchange is proposed as a generalized transposition that affects the chromosome by swapping two non-intersecting segments of genes. The problem of sorting by block-interchanges is to find a minimum series of block-interchanges for sorting one chromosome into another. In this paper, we present an O(n + delta log delta) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O(delta n) time proposed by Lin et al. (2005) [14], where n is the number of genes and delta is the minimum number of block-interchanges required to sort a chromosome. (C) 2010 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.ipl.2010.03.003
http://hdl.handle.net/11536/5619
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2010.03.003
期刊: INFORMATION PROCESSING LETTERS
Volume: 110
Issue: 8-9
起始頁: 345
結束頁: 350
顯示於類別:期刊論文


文件中的檔案:

  1. 000276860400015.pdf