کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9600490 | 1404692 | 2005 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sorting by Restricted-Length-Weighted Reversals
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
علوم زیستی و بیوفناوری
بیوشیمی، ژنتیک و زیست شناسی مولکولی
ژنتیک
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Sorting by Restricted-Length-Weighted Reversals Sorting by Restricted-Length-Weighted Reversals](/preview/png/9600490.png)
چکیده انگلیسی
Classical sorting by reversals uses the unit-cost model, that is, each reversal consumes an equal cost. This model limits the biological meaning of sorting by reversal. Bender and his colleagues extended it by assigning a cost function f(l) = lα for all α ⥠0, where l is the length of the reversed subsequence. In this paper, we extend their results by considering a model in which long reversals are prohibited. Using the same cost function above for permitted reversals, we present tight or nearly tight bounds for the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given 0/1 sequence as well as a given permutation. Our proposed problems are more biologically meaningful and more algorithmically general and challenging than the problem considered by Bender et al. Furthermore, our bounds are tight and nearly tight, whereas our algorithms provide good approximation ratios compared to the optimal cost to sort 0/1 sequences or permutations by reversals.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Genomics, Proteomics & Bioinformatics - Volume 3, Issue 2, 2005, Pages 120-127
Journal: Genomics, Proteomics & Bioinformatics - Volume 3, Issue 2, 2005, Pages 120-127
نویسندگان
Thach Cam Nguyen, Hieu Trung Ngo, Nguyen Bao Nguyen,