Source:http://linkedlifedata.com/resource/pubmed/id/18649439
Switch to
| Predicate | Object |
|---|---|
| rdf:type | |
| lifeskim:mentions | |
| pubmed:issue |
2
|
| pubmed:dateCreated |
2008-7-23
|
| pubmed:abstractText |
For the first time, we study the sorting of permutations by length-weighted transpositions under a wide class of cost functions, namely f(l)=l(alpha), where l is the length of the transposition. For different alpha, we give corresponding upper and lower bounds of the cost of sorting any binary sequences or any permutations. Furthermore, an O(log n)-approximation algorithm and an exact algorithm are given to determine the optimal transposition series of sorting a permutation of length n when 1< alpha < 2 and alpha > or =2 respectively. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.
|
| pubmed:language |
eng
|
| pubmed:journal | |
| pubmed:citationSubset |
IM
|
| pubmed:status |
MEDLINE
|
| pubmed:issn |
1744-5485
|
| pubmed:author | |
| pubmed:issnType |
Print
|
| pubmed:volume |
4
|
| pubmed:owner |
NLM
|
| pubmed:authorsComplete |
Y
|
| pubmed:pagination |
164-71
|
| pubmed:meshHeading | |
| pubmed:year |
2008
|
| pubmed:articleTitle |
Sorting by transpositions: dealing with length-weighted models.
|
| pubmed:affiliation |
Department of Applied Mathematics, Shandong University at Weihai, Weihai, China. qixingqin@163.com
|
| pubmed:publicationType |
Journal Article,
Research Support, Non-U.S. Gov't
|