کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875457 | 1441955 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Can a breakpoint graph be decomposed into none other than 2-cycles?
ترجمه فارسی عنوان
آیا می توان یک گراف نقطه پایانی به غیر از 2 سیکل تجزیه شود؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم، پیچیدگی، نمودار شکستن نقطه، بازسازی ژنوم، تجزیه چرخه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Breakpoint graph has been widely used as a key data structure in algorithm design for genome rearrangements. The problem of breakpoint graph cycle decomposition, which asks for a largest collection of edge-disjoint cycles, is crucial in computing rearrangement distances between genomes. This problem is NP-hard, and can be approximated to 1.4193+ϵ. It is still open for deciding whether a breakpoint graph can admit a cycle decomposition with none other than 2-cycles. In this paper, we present a linear time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 38-45
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 38-45
نویسندگان
Lianrong Pu, Yu Lin, Daming Zhu, Haitao Jiang,