کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657193 | 688083 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach
دانلود مقاله + سفارش ترجمه
دانلود مقاله 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](/preview/png/9657193.png)
چکیده انگلیسی
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
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2â4, June 2005, Pages 342-361
نویسندگان
Maria Emilia M.T. Walter, Mauro C. Sobrinho, Eugenia T.G. Oliveira, Lorena S. Soares, Adilton G. Oliveira, Thelmo E.S. Martins, Tiago M. Fonseca,