کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431603 688594 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Alphabet-independent algorithms for finding context-sensitive repeats in linear time
ترجمه فارسی عنوان
الگوریتم های مستقل الفبا برای یافتن تکرار حساس به متن در زمان خطی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The identification of repetitive sequences (repeats) is an essential component of genome sequence analysis, and there are dozens of algorithms that search for exact or approximate repeats. The notions of maximal and supermaximal (exact) repeats have received special attention, and it is possible to simultaneously compute them on index data structures like the suffix tree or the enhanced suffix array. Very recently, this research has been extended in two directions. Gallé and Tealdi [10] devised an alphabet-independent linear-time algorithm that finds all context-diverse repeats (which subsume maximal and supermaximal repeats as special cases), while Taillefer and Miller [31] gave a quadratic-time algorithm that simultaneously computes and classifies maximal, near-supermaximal, and supermaximal repeats. In this paper, we provide new alphabet-independent linear-time algorithms for both tasks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 23–36
نویسندگان
, ,