An improved algorithm for sorting by block-interchanges based on permutation groups

Yen Lin Huang; Cheng Chen Huang; Chuan Yi Tang; Chin Lung Lu

doi:10.1016/j.ipl.2010.03.003

An improved algorithm for sorting by block-interchanges based on permutation groups

Yen Lin Huang
, Cheng Chen Huang
, Chuan Yi Tang
, Chin Lung Lu^*

^*Corresponding author for this work

National Tsing Hua University
National Yang Ming Chiao Tung University

Research output: Contribution to journal › Journal Article › peer-review

9 Scopus citations

Abstract

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 + δ log δ) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O (δ n) time proposed by Lin et al. (2005) [14], where n is the number of genes and δ is the minimum number of block-interchanges required to sort a chromosome.

Original language	English
Pages (from-to)	345-350
Number of pages	6
Journal	Information Processing Letters
Volume	110
Issue number	8-9
DOIs	https://doi.org/10.1016/j.ipl.2010.03.003
State	Published - 01 04 2010
Externally published	Yes

Keywords

Algorithm
Block-interchange
Data structure
Generalized transposition
Genome rearrangement
Permutation group
Permutation tree

Access to Document

10.1016/j.ipl.2010.03.003

Cite this

@article{ed581389653f4b2abc8590b6e2c7d85f,

title = "An improved algorithm for sorting by block-interchanges based on permutation groups",

abstract = "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 + δ log δ) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O (δ n) time proposed by Lin et al. (2005) [14], where n is the number of genes and δ is the minimum number of block-interchanges required to sort a chromosome.",

keywords = "Algorithm, Block-interchange, Data structure, Generalized transposition, Genome rearrangement, Permutation group, Permutation tree",

author = "Huang, \{Yen Lin\} and Huang, \{Cheng Chen\} and Tang, \{Chuan Yi\} and Lu, \{Chin Lung\}",

year = "2010",

month = apr,

day = "1",

doi = "10.1016/j.ipl.2010.03.003",

language = "英语",

volume = "110",

pages = "345--350",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "8-9",

}

TY - JOUR

T1 - An improved algorithm for sorting by block-interchanges based on permutation groups

AU - Huang, Yen Lin

AU - Huang, Cheng Chen

AU - Tang, Chuan Yi

AU - Lu, Chin Lung

PY - 2010/4/1

Y1 - 2010/4/1

N2 - 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 + δ log δ) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O (δ n) time proposed by Lin et al. (2005) [14], where n is the number of genes and δ is the minimum number of block-interchanges required to sort a chromosome.

AB - 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 + δ log δ) time algorithm for solving the problem of sorting by block-interchanges, which improves a previous algorithm of O (δ n) time proposed by Lin et al. (2005) [14], where n is the number of genes and δ is the minimum number of block-interchanges required to sort a chromosome.

KW - Algorithm

KW - Block-interchange

KW - Data structure

KW - Generalized transposition

KW - Genome rearrangement

KW - Permutation group

KW - Permutation tree

UR - https://www.scopus.com/pages/publications/77949492205

U2 - 10.1016/j.ipl.2010.03.003

DO - 10.1016/j.ipl.2010.03.003

M3 - 文章

AN - SCOPUS:77949492205

SN - 0020-0190

VL - 110

SP - 345

EP - 350

JO - Information Processing Letters

JF - Information Processing Letters

IS - 8-9

ER -

An improved algorithm for sorting by block-interchanges based on permutation groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this