An efficient algorithm for one-sided block ordering problem under block-interchange distance

Kun Tze Chen, Chi Long Li, Hsien Tai Chiu, Chin Lung Lu

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

In this work, we study the one-sided block ordering problem under block-interchange distance. Given two signed permutations π and σ of size n, where π represents a partially assembled genome consisting of several blocks (i.e., contigs) and σ represents a completely assembled genome, the one-sided block ordering problem under block-interchange distance is to order (i.e., assemble) the blocks of π such that the block-interchange distance between the assembly of π and σ is minimized. The one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups in algebra, we design an efficient algorithm to solve the one-sided block ordering problem under block-interchange distance in O(nlogn) time. Moreover, we show that the assembly of π can be done in O(n) time and its block-interchange distance from σ can also be calculated in advance in O(n) time.

Original languageEnglish
Pages (from-to)296-305
Number of pages10
JournalTheoretical Computer Science
Volume609
DOIs
Publication statusPublished - 2016 Jan 4

Fingerprint

Interchanges
Genome
Efficient Algorithms
Genes
Signed Permutations
Permutation group
Algebra

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{db53fadc2cdb4ebaaa53eca90a3abe87,
title = "An efficient algorithm for one-sided block ordering problem under block-interchange distance",
abstract = "In this work, we study the one-sided block ordering problem under block-interchange distance. Given two signed permutations π and σ of size n, where π represents a partially assembled genome consisting of several blocks (i.e., contigs) and σ represents a completely assembled genome, the one-sided block ordering problem under block-interchange distance is to order (i.e., assemble) the blocks of π such that the block-interchange distance between the assembly of π and σ is minimized. The one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups in algebra, we design an efficient algorithm to solve the one-sided block ordering problem under block-interchange distance in O(nlogn) time. Moreover, we show that the assembly of π can be done in O(n) time and its block-interchange distance from σ can also be calculated in advance in O(n) time.",
author = "Chen, {Kun Tze} and Li, {Chi Long} and Chiu, {Hsien Tai} and Lu, {Chin Lung}",
year = "2016",
month = "1",
day = "4",
doi = "10.1016/j.tcs.2015.10.010",
language = "English",
volume = "609",
pages = "296--305",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

An efficient algorithm for one-sided block ordering problem under block-interchange distance. / Chen, Kun Tze; Li, Chi Long; Chiu, Hsien Tai; Lu, Chin Lung.

In: Theoretical Computer Science, Vol. 609, 04.01.2016, p. 296-305.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An efficient algorithm for one-sided block ordering problem under block-interchange distance

AU - Chen, Kun Tze

AU - Li, Chi Long

AU - Chiu, Hsien Tai

AU - Lu, Chin Lung

PY - 2016/1/4

Y1 - 2016/1/4

N2 - In this work, we study the one-sided block ordering problem under block-interchange distance. Given two signed permutations π and σ of size n, where π represents a partially assembled genome consisting of several blocks (i.e., contigs) and σ represents a completely assembled genome, the one-sided block ordering problem under block-interchange distance is to order (i.e., assemble) the blocks of π such that the block-interchange distance between the assembly of π and σ is minimized. The one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups in algebra, we design an efficient algorithm to solve the one-sided block ordering problem under block-interchange distance in O(nlogn) time. Moreover, we show that the assembly of π can be done in O(n) time and its block-interchange distance from σ can also be calculated in advance in O(n) time.

AB - In this work, we study the one-sided block ordering problem under block-interchange distance. Given two signed permutations π and σ of size n, where π represents a partially assembled genome consisting of several blocks (i.e., contigs) and σ represents a completely assembled genome, the one-sided block ordering problem under block-interchange distance is to order (i.e., assemble) the blocks of π such that the block-interchange distance between the assembly of π and σ is minimized. The one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups in algebra, we design an efficient algorithm to solve the one-sided block ordering problem under block-interchange distance in O(nlogn) time. Moreover, we show that the assembly of π can be done in O(n) time and its block-interchange distance from σ can also be calculated in advance in O(n) time.

UR - http://www.scopus.com/inward/record.url?scp=84951267649&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84951267649&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.10.010

DO - 10.1016/j.tcs.2015.10.010

M3 - Article

AN - SCOPUS:84951267649

VL - 609

SP - 296

EP - 305

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -