کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426967 686385 2006 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A simpler and faster 1.5-approximation algorithm for sorting by transpositions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A simpler and faster 1.5-approximation algorithm for sorting by transpositions
چکیده انگلیسی

An important problem in genome rearrangements is sorting permutations by transpositions. The complexity of the problem is still open, and two rather complicated 1.5-approximation algorithms for sorting linear permutations are known (Bafna and Pevzner, 98 and Christie, 99). The fastest known algorithm is the quadratic algorithm of Bafna and Pevzner. In this paper, we observe that the problem of sorting circular permutations by transpositions is equivalent to the problem of sorting linear permutations by transpositions. Hence, all algorithms for sorting linear permutations by transpositions can be used to sort circular permutations. Our main result is a new 1.5-approximation algorithm, which is considerably simpler than the previous ones, and whose analysis is significantly less involved.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 204, Issue 2, February 2006, Pages 275-290