بترکه چشم حسود    

جستجوی پیشرفته مقالات

     عنوان:

نماد اعتماد الکترونیکی

logo-samandehi

لیست مقالات ترجمه شده

سایر مقالات

امروز
دیروز
هفته جاری
هفته گذشته
ماه جاری
ماه گذشته
بازدید کل
4534
7119
35804
5226456
123944
192538
5552708

آی‌پی شما: 54.242.25.198
امروز: پنج شنبه، 30 خرداد 1398 شمسی ساعت به وقت گرینویچ: 21:03:45

توجه                           توجه

تمامی مقالات ترجمه شده در قالب فایل ورد (Word)  ارائه می‌شوند.


       دسته‌بندی: مقالات نظریه ماشین       فروش: 0 بازدید: 4866
انطباق رشته با شکاف های طول متغیر
    قیمت محصول: 200000 ریال



 

String Matching with Variable Length Gaps

Abstract

We consider string matching with variable length gaps. Given a string T and a pattern P consisting of strings separated by variable length gaps (arbitrary strings of length in a specified range), the problem is to find all ending positions of substrings in T that match P. This problem is a basic primitive in computational biology applications. Let m and n be the lengths of P and T , respectively, and let k be the number of strings in P. We present a new algorithm achieving time O(n log k+m+α) and space O(m+A), where A is the sum of the lower bounds of the lengths of the gaps in P and α is the total number of occurrences of the strings in P within T . Compared to the previous results this bound essentially achieves the best known time and space complexities simultaneously. Consequently, our algorithm obtains the best known bounds for almost all combinations of m, n, k, A, and α. Our algorithm is surprisingly simple and straightforward to implement. We also present algorithms for finding and encoding the positions of all strings in P for every match of the pattern.

 

pdfدانلود رایگان مقاله انگلیسی              196.49 KB

 

چکیده
انطباق رشته را با شکاف های طول متغیر در نظر می گیریم. با در نظر گرفتن رشته T و الگوی P متشکل از رشته های جدا شده توسط شکاف های طول متغیر (رشته هایی با طول اختیاری در محدوده مشخص)، مسئله، یافتن تمام مکان های انتهایی زیررشته ها در T می باشد که منطبق با P می باشند. این مسئله، یک اصل پایه در کاربردهای بیولوژی محاسباتی می باشد. فرض کنید m و n بترتیب طول های P و T می باشند و k تعداد رشته ها در P می باشد. الگوریتم جدیدی را با دستیابی به زمان O(nlog k + m + α) و مکان O(m+A) ارائه می کنیم، که در آن A مجموع کران های پایین طول های شکاف ها در P می باشد و α کل تعداد وقوع های رشته ها در P درون T می باشد. در مقایسه با نتایج قبلی، این کران در اصل همزمان به بهترین پیچیدگی های زمانی و مکانی مشخص دست می یابد. در نتیجه، الگوریتم ما به بهترین کران های مشخص برای تقریبا تمام ترکیب های m، n، k، a و α دست می یابد. الگوریتم ما پیاده سازی آسان و ساده ای دارد. همچنین الگوریتم هایی برای یافتن و کدگذاری مکان های تمام رشته ها در P برای هر انطباق الگو ارائه می کنیم.

 

تعداد صفحات مقاله انگلیسی: 15 صفحه
تعداد صفحات مقاله فارسی: 28 صفحه


لینک دانلود فایل خریداری شده بلافاصله بعد از پرداخت آنلاین فعال می‌شود