کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431119 | 688278 | 2008 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An approximation algorithm for sorting by reversals and transpositions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ2.8386+δ for any δ>0δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 449–457
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 449–457
نویسندگان
Atif Rahman, Swakkhar Shatabda, Masud Hasan,