کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439121 690448 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient construction of maximal and minimal representations of motifs of a string
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Efficient construction of maximal and minimal representations of motifs of a string
چکیده انگلیسی

Two substrings of a given text string are called synchronous (occurrence-equivalent) if their sets of occurrence locations are translates of each other. Linear time algorithms are given for the problems of finding a shortest and a longest substring that is synchronous with a given substring. We also introduce approximate variants of the motif discovery problem and give polynomial time algorithms for finding longest and shortest substrings whose suitably translated occurrence location set contains or, respectively, is contained in a given set of locations. The FFT technique used here also leads to an O(nlogn) algorithm for finding the maximum-content gapped motif that is synchronous with a given set of locations; the previously known algorithm for this problem is only quadratic.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 30–32, 20 August 2009, Pages 2999-3005