An improved algorithm for sorting by block-interchanges based on permutation groups
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
350 | en_US |
dc.citation.issue |
8-9 | en_US |
dc.citation.spage |
345 | en_US |
dc.citation.volume |
110 | en_US |
dc.citation.woscount |
1 | |
dc.contributor.author |
Huang, Yen-Lin | en_US |
dc.contributor.author |
Huang, Cheng-Chen | en_US |
dc.contributor.author |
Tang, Chuan Yi | en_US |
dc.contributor.author |
Lu, Chin Lung | en_US |
dc.contributor.department |
生物科技學系 | zh_TW |
dc.contributor.department |
生物資訊及系統生物研究所 | zh_TW |
dc.contributor.department |
Department of Biological Science and Technology | en_US |
dc.contributor.department |
Institude of Bioinformatics and Systems Biology | en_US |
dc.date.accessioned |
2014-12-08T15:07:09Z | |
dc.date.available |
2014-12-08T15:07:09Z | |
dc.date.issued |
2010-04-01 | en_US |
dc.description.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 + 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. | en_US |
dc.identifier.doi |
10.1016/j.ipl.2010.03.003 | en_US |
dc.identifier.issn |
0020-0190 | en_US |
dc.identifier.journal |
INFORMATION PROCESSING LETTERS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.ipl.2010.03.003 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/5619 | |
dc.identifier.wosnumber |
WOS:000276860400015 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Algorithm | en_US |
dc.subject |
Data structure | en_US |
dc.subject |
Genome rearrangement | en_US |
dc.subject |
Permutation group | en_US |
dc.subject |
Block-interchange | en_US |
dc.subject |
Generalized transposition | en_US |
dc.subject |
Permutation tree | en_US |
dc.title |
An improved algorithm for sorting by block-interchanges based on permutation groups | en_US |
dc.type |
Article | en_US |
檔案
- 000276860400015.pdf (198.2 KB, Adobe PDF)
所屬典藏: 期刊論文