کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9657193 688083 2005 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach
چکیده انگلیسی
In computational biology, genome rearrangements is a field in which we investigate the combinatorial problem of sorting by transpositions. This problem consists in finding the minimum number of transpositions (mutational event) that transform a chromosome into another. Bafna and Pevzner [SIAM J. 11 (2) (1998) 224-240] proposed a 1.5-approximation algorithm to solve this problem, using a structure called cycle graph. In this work, we first present results that allowed us to implement their algorithm, maintaining the 1.5-approximation ratio. The present implementation runs in O(n3) time complexity, noting that we created a data structure to store the cycle graph in memory in O(n) time complexity. The results obtained from the program allowed us to propose heuristics, that further improved the performance of the original algorithm. Comparing our experimental results with the best results published so far, we achieved better performance. Besides, we developed a program to visualize the cycle graphs and the transpositions indicated by the algorithm. This work targets to contribute for discovering the complexity of the problem of sorting by transpositions, which remains open.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2–4, June 2005, Pages 342-361
نویسندگان
, , , , , , ,