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 language | English |
|---|---|
| Pages (from-to) | 296-305 |
| Number of pages | 10 |
| Journal | Theoretical Computer Science |
| Volume | 609 |
| DOIs | |
| Publication status | Published - 2016 Jan 4 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
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 journal › Article
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 -