جستجوی موتیف کاشته‌شده
در زمینه زیست شناسی محاسباتی، جستجوی دنباله موتیف کاشته شده (PMS)، که با عنوان جست و جوی موتیف (L، d) نیز شناخته شده می شود، مسئله ی شناسایی توالی های حفظ شده در مجموعه ای از توالی های نوکلئیک اسید (مانند توالی دی‌ان‌ای) یا آمینواسید (مانند توالی پروتئین) می باشد.
پیدا کردن موتیف کاشته شده یک مسئله ی NP-کامل است. پیچیدگی زمانی اغلب الگوریتم های مطرح شده برای این مسئله، به صورت نمایی به مجموعه حروف الفبای مسئله و طول موتیف ("L") بستگی دارد. مسئله ی PMS ابتدا توسط Keich و Pevzner و در سال 2002 معرفی شده است.
مسئله‌ی شناسایی الگوهای معنی دار (از جمله موتیف) از داده های بیولوژیکی به شدت مورد مطالعه قرار گرفته است، زیرا آنها نقش حیاتی در درک عملکرد ژن و بیماری های انسانی دارند و ممکن است به عنوان اهداف دارویی درمان قرار بگیرند.
نشانه‌های ریاضی به کاررفته در توصیف مسئله‌ PMS، از قرار زیر است.
S = {"s, s, s, …, s"} رشته هایی هستند که در ورودی داده شده اند هر کدام از الفبای Σ تشکیل شده اند. به زیررشته هایی به طول L از هر کدام از این رشته ها، L-mer می گویند. در صورتی که a و b دو L-mer باشند،"d(a, b)" را برابر فاصله همینگ بین a و b تعریف می کنیم. همجنین اگر s یکی از رشته هایی باشد که در ورودی داده شده است، "d(a, s)" را برابر فاصله ی همینگ کمینه بین a و همه ی L-mer هایی مانند b از رشته ی s تعریف می کنیم. حال اگر S را برابر مجموعه ی همه ی رشته هایی بگیریم که در ورودی داده شده است، "d(a, S)" را برابر max"d(a, s)" تعریف می کنیم. همجنین با فرض اینکه u یک L-mer دلخواه باشد، "d"-همسایگی "u" را برابر مجموعه ی همه ی L-mer های "v" می گیریم که فاصله ی همینگ آن ها از u، کمتر و یا مساوی d باشد (d(u, v)" ≤ "d) و آن را با B(u) نشان می دهیم. با فرض اینکه a و b دو L-mer دلخواه باشند، همه ی L-mer هایی که هم از x و هم از y ، فاصله ی همینگ کمتر و یا مساوی d دارند را با "B(x, y)" نشان می دهیم. این نمادگذاری قابل تعمیم برای بیشتر از دو L-mer نیز می باشد ("B(x, y, z)" و ...).
صورت مسئله ی جست و جوی موتیف به صورت خلاصه از قرار زیر است.
ورودی مسئله، شامل n رشته ی (s, s, … , s) که هر کدام به طول m می باشد و از حروف الفبای Σ ایجاد شده اند. همچنین دو عدد طبیعی L و d نیز در ورودی داده می شود. همه ی رشته هایی مانند X به طول "L" را می خواهیم، به طوریکه هر کدام از رشته های ورودی، شامل یک زیررشته به طول "L" می باشند به طوریکه فاصله همینگ آن زیر رشته با X، حداکثر d باشد. هر کدام از این رشته های X، یک موتیف (L، d) نامیده می شوند. این مسئله معمولاً با عنوان جست و جوی موتیف (L، d) شناخته می شود. به عنوان مثال، با ورودی های GCGCGAT ،CACGTGA و CGGTGCC و همچنین d = 1 و L = 3 ، رشته ی GGT یک موتیف برای رشته ها می باشد.توجه شود که در رشته ی اول، زیررشته ی CGT، با فاصله همینگ 1 از موتیف GGT می باشد، همچنین در رشته ی دوم، GAT و در رشته ی سوم، GGT، نمونه های موتیف در رشته ها می باشند. معمولاً مسئله ی پیدا کردن موتیف، در توالی دی‌ان‌ای بررسی می شود، که در این حالت دارم: Σ ={G, C, T, A}. در صورتی هم که این مسئله در حوزه ی پروتئین بررسی شود، الفبای آن شامل 20 نوع اسیدآمینه می شود.
الگوریتم های بسیاری برای این مسئله پیشنهاد شده اند. این الگوریتم های را می توان به دو دسته ی الگوریتم های تقریبی و الگوریتم های دقیق دسته بندی کرد. جوابی که از الگوریتم های دقیق می گیریم، جواب بهینه است، ولی الگوریتم های تقریبی همواره جواب بهینه نمی دهند. برخی از الگوریتم های تقریبی برای پیدا کردن موتیف ها شامل Random Projection, PatternBranching، MULTIPROFILER، CONSENSUS، و ProfileBranching. می باشند.
روش‌های دقیق پیدا کردن موتیف، به دو دسته‌ی شمارشی و روش‌های بر مبنای الگوریتم امید ریاضی–بیشینه کردن تقسیم می‌شوند. در روش‌های شمارشی، کل فضای مسئله برای پیدا کردن جواب، جست‌وجو می‌شود. معروفترین الگوریتم‌هایی که با این روش دنباله‌ی موتیف را پیدا می‌کنند، YMF و Pavesi et all می‌باشند. سری الگوریتم‌های PMS که در آزمایشگاه Rajasekaran گسترش یافته‌اند، هم به عنوان مهمترین نوع الگوریتم‌های بیشینه‌سازی امید ریاضی مطرح شده‌اند.
با دانستن طول موتیف (L) معلوم می‌شود که موتیف‌ها، از میان formula_1 رشته به طول L انتخاب خواهند شد. در ننیجه می‌توان با جست‌وجو میان تمام L-merها، موتیف‌ها را پیدا کرد. اگر محل شروع موتیف در هر کدام از رشته‌های ورودی را ندانیم، زمان اجرای این الگوریتم، formula_2 می‌شود، که در آن n، تعداد رشته‌های ورودی و m، طول هر کدام از رشته‌ها می‌باشد.
با استفاده از این الگوریتم، موتیف با بیشترین امتیاز را پیدا می‌کنیم. امتیاز موتیف را برابر مجموع فاصله‌ی همینگ رشته‌ها از موتیف در نظر می‌گریم. در این الگوریتم، با استفاده از یک گراف جست‌وجو، فضای مسئله بهینه‌تر جست‌وجو می‌شود. برای این‌کار، یک درخت دودویی کامل می‌سازیم که برگ‌های آن، کل L-mer ها هستند. هر یک از رأس‌های داخلی هم پیشوند فرزندان خود هستند. روش کار این الگوریتم، مانند هرس آلفا بتا می‌باشد، که بخشی از فضای جست‌وجو هرس می‌شود. هنگامی که امتیاز یک رأس داخلی، بیشتر از بهترین امتیازی باشد که تا کنون پیدا شده‌است، دیگر زیردرخت آن را جست‌وجو نمی‌کنیم و هرس می‌کنیم.