کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10333036 688187 2005 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A 1.5-approximation algorithm for sorting by transpositions and transreversals
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A 1.5-approximation algorithm for sorting by transpositions and transreversals
چکیده انگلیسی
One of the most promising ways to determine evolutionary distance between two organisms is to compare the order of appearance of orthologous genes in their genomes. The resulting genome rearrangement problem calls for finding a shortest sequence of rearrangement operations that sorts one genome into the other. In this paper we provide a 1.5-approximation algorithm for the problem of sorting by transpositions and transreversals, improving on a five-year-old 1.75 ratio for this problem. Our algorithm is also faster than current approaches and requires O(n3/2logn) time for n genes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 70, Issue 3, May 2005, Pages 300-320
نویسندگان
, ,