. متن داده‌شده را خلاصه کن

متن: نشانه‌های ریاضی به‌کاررفته در توصیف مسئله pms، از قرار زیر است. s = s ۱ , s ۲ , s ۳ , …, sn رشته‌های به طول m هستند که در ورودی داده شده‌اند هر کدام از الفبای σ تشکیل شده‌اند. به زیررشته‌هایی به طول l از هر کدام از این رشته‌ها، l-mer می‌گویند. در صورتی که a و b دو l-mer باشند، را برابر فاصله همینگ بین a و b تعریف می‌کنیم. همچنین اگر s یکی از رشته‌هایی باشد که در ورودی داده‌شده است، را برابر فاصله‌ی همینگ کمینه بین a و همه‌ی l-mer هایی مانند b از رشته‌ی s تعریف می‌کنیم. حال اگر s را برابر مجموعه‌ی همه‌ی رشته‌هایی بگیریم که در ورودی داده‌شده است، را برابر max تعریف می‌کنیم. همچنین با فرض اینکه u یک l-mer دلخواه باشد، d-همسایگی u را برابر مجموعه‌ی همه‌ی l-mer‌های v می‌گیریم که فاصله‌ی همینگ آن‌ها از u، کمتر و یا مساوی d باشد () و آن را با () نشان می‌دهیم. با فرض اینکه a و b دو l-mer دلخواه باشند، همه‌ی l-mer هایی که هم از x و هم از y، فاصله‌ی همینگ کمتر و یا مساوی d دارند را با () نشان می‌دهیم. این نمادگذاری قابل تعمیم برای بیشتر از دو l-mer نیز می‌باشد (bd (x, y, z) و …). صورت مسئله‌ی جستجوی موتیف به صورت خلاصه از قرار زیر است. ورودی مسئله، شامل n رشته‌ی (s ۱ , s ۲ , … , sn) که هر کدام به طول m می‌باشد و از حروف الفبای σ ایجاد شده‌اند. همچنین دو عدد طبیعی l و d نیز در ورودی داده می‌شود. همه‌ی رشته‌هایی مانند x به طول l را می‌خواهیم، به طوریکه هر کدام از رشته‌های ورودی، شامل یک زیررشته به طول l می‌باشند به طوریکه فاصله همینگ آن زیر رشته با x، حداکثر d باشد. هر کدام از این رشته‌های x، یک موتیف (l، d) نامیده می‌شوند. این مسئله معمولا با عنوان جستجوی موتیف (l، d) شناخته می‌شود. به عنوان مثال، با ورودی‌های gcgcgat، cacgtga و cggtgcc و همچنین d = ۱ و l = ۳، رشته‌ی ggt یک موتیف برای رشته‌ها می‌باشد. توجه شود که در رشته‌ی اول، زیررشته‌ی cgt، با فاصله همینگ ۱ از موتیف ggt می‌باشد، همچنین در رشته‌ی دوم، gat و در رشته‌ی سوم، ggt، نمونه‌های موتیف در رشته‌ها می‌باشند. معمولا مسئله‌ی پیدا کردن موتیف، در توالی دی‌ان‌ای بررسی می‌شود، که در این حالت دارم: {σ = {g, c, t, a. در صورتی هم که این مسئله در حوزه‌ی پروتئین بررسی شود، الفبای آن شامل ۲۰ نوع اسیدآمینه می‌شود. الگوریتم‌های بسیاری برای …
خلاصه:
در زمینه زیست شناسی محاسباتی ، جستجوی دنباله موتیف کاشته شده (pms) ، که با عنوان جستجوی موتیف (l ، d) نیز شناخته شده می‌شود ، مسئله‌ی شناسایی توالی‌های حفظ شده در مجموعه‌ای از توالی‌های نوکلئیک اسید (مانند توالی دی‌ان‌ای) یا آمینواسید (مانند توالی پروتئین) می‌باشد . پیدا کردن موتیف کاشته شده یک مسئله‌ی np-کامل است . پیچیدگی زمانی اغلب الگوریتم‌های مطرح شده برای این مسئله ، به صورت نمایی به مجموعه حروف الفبای مسئله و طول موتیف (l) بستگی دارد . مسئله‌ی pms ابتدا توسط keich و pevzner و در سال ۲۰۰۲ معرفی شده است .