Browsing by Author "Huang, Cheng-Chen"

Now showing 1 - 1 of 1

An improved algorithm for sorting by block-interchanges based on permutation groups
(2010-04-01)
Huang, Yen-Lin
;
Huang, Cheng-Chen
;
Tang, Chuan Yi
;
Lu, Chin Lung
;
生物科技學系
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.