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

研究成果: Article同行評審

3 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)296-305
頁數10
期刊Theoretical Computer Science
609
DOIs
出版狀態Published - 2016 1月 4

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「An efficient algorithm for one-sided block ordering problem under block-interchange distance」主題。共同形成了獨特的指紋。

引用此