جستجوی موتیف گماشته‌شده

در زمینه زیست شناسی محاسباتی، جستجوی دنباله موتیف کاشته شده (PMS)، که با عنوان جستجوی موتیف (L، d) نیز شناخته شده می شود، مسئله ی شناسایی توالی های حفظ شده در مجموعه ای از توالی های نوکلئیک اسید (مانند توالی دی‌ان‌ای) یا آمینواسید (مانند توالی پروتئین) می باشد.

پیدا کردن موتیف کاشته شده یک مسئله ی NP-کامل است. پیچیدگی زمانی اغلب الگوریتم های مطرح شده برای این مسئله، به صورت نمایی به مجموعه حروف الفبای مسئله و طول موتیف (L) بستگی دارد. مسئله ی PMS ابتدا توسط Keich و Pevzner و در سال 2002 معرفی شده است.^[۱]

مسئله‌ی شناسایی الگوهای معنی دار (از جمله موتیف) از داده های بیولوژیکی به شدت مورد مطالعه قرار گرفته است، زیرا آنها نقش حیاتی در درک عملکرد ژن و بیماری های انسانی دارند و ممکن است به عنوان اهداف دارویی درمان قرار بگیرند.

نشانه‌های به کاررفته

نشانه‌های ریاضی به کاررفته در توصیف مسئله PMS، از قرار زیر است.

S = s₁, s₂, s₃, …, s_n رشته‌های به طول m هستند که در ورودی داده شده اند هر کدام از الفبای Σ تشکیل شده اند. به زیررشته هایی به طول L از هر کدام از این رشته ها، L-mer می گویند. در صورتی که a و b دو L-mer باشند، $d_{H}(a,b)$ را برابر فاصله همینگ بین a و b تعریف می کنیم. همچنین اگر s یکی از رشته هایی باشد که در ورودی داده شده است، $d_{H}(a,s)$ را برابر فاصله ی همینگ کمینه بین a و همه ی L-mer هایی مانند b از رشته ی s تعریف می کنیم. حال اگر S را برابر مجموعه ی همه ی رشته هایی بگیریم که در ورودی داده شده است، $d_{H}(a,S)$ را برابر $s\in S,d_{H}(a,s)$ max تعریف می کنیم. همچنین با فرض اینکه u یک L-mer دلخواه باشد، d-همسایگی u را برابر مجموعه ی همه ی L-mer های v می گیریم که فاصله ی همینگ آن ها از u، کمتر و یا مساوی d باشد ( $d_{H}(u,v)\leq d$ ) و آن را با ( $B_{d}(u)$ ) نشان می دهیم. با فرض اینکه a و b دو L-mer دلخواه باشند، همه ی L-mer هایی که هم از x و هم از y ، فاصله ی همینگ کمتر و یا مساوی d دارند را با ( $B_{d}(x,y)$ ) نشان می دهیم. این نمادگذاری قابل تعمیم برای بیشتر از دو L-mer نیز می باشد (B_d(x, y, z) و ...).

صورت مسئله

صورت مسئله ی جستجوی موتیف به صورت خلاصه از قرار زیر است.

ورودی مسئله، شامل n رشته ی (s₁, s₂, … , s_n) که هر کدام به طول 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 al می‌باشند. سری الگوریتم‌های PMS که در آزمایشگاه Rajasekaran بایگانی‌شده در ۲۳ دسامبر ۲۰۱۸ توسط Wayback Machine گسترش یافته‌اند، هم به عنوان مهمترین نوع الگوریتم‌های بیشینه‌سازی امید ریاضی مطرح شده‌اند.

الگوریتم YMF

با دانستن طول موتیف (L) معلوم می‌شود که موتیف‌ها، از میان $4^{L}$ رشته به طول L انتخاب خواهند شد. در نتیجه می‌توان با جستجو میان تمام L-merها، موتیف‌ها را پیدا کرد. اگر محل شروع موتیف در هر کدام از رشته‌های ورودی را ندانیم، زمان اجرای این الگوریتم، $O(Lm^{n})$ می‌شود، که در آن n، تعداد رشته‌های ورودی و m، طول هر کدام از رشته‌ها می‌باشد.

الگوریتم Pavesi

با استفاده از این الگوریتم، موتیف با بیشترین امتیاز را پیدا می‌کنیم. امتیاز موتیف را برابر مجموع فاصله‌ی همینگ رشته‌ها از موتیف در نظر می‌گریم. در این الگوریتم، با استفاده از یک گراف جستجو، فضای مسئله بهینه‌تر جستجو می‌شود. برای این‌کار، یک درخت دودویی کامل می‌سازیم که برگ‌های آن، کل L-mer ها هستند. هر یک از رأس‌های داخلی هم پیشوند فرزندان خود هستند. روش کار این الگوریتم، مانند هرس آلفا بتا می‌باشد، که بخشی از فضای جستجو هرس می‌شود. هنگامی که امتیاز یک رأس داخلی، بیشتر از بهترین امتیازی باشد که تا کنون پیدا شده‌است، دیگر زیردرخت آن را جستجو نمی‌کنیم و هرس می‌کنیم.

پانویس

↑ ^۱٫۰ ^۱٫۱ Keich, U.; Pevzner, P. A. (October 2002). "Finding motifs in the twilight zone". Bioinformatics. 18 (10): 1374–1381. doi:10.1093/bioinformatics/18.10.1374. PMID 12376382.
↑ Buhler, J.; Tompa, M. (2002). "Finding motifs using random projections". J. Comput. Biol. 9 (2): 225–242. CiteSeerX 10.1.1.26.2491. doi:10.1089/10665270252935430. PMID 12015879.
↑ ^۳٫۰ ^۳٫۱ Price, A.; Ramabhadran, S.; Pevzner, P. A. (October 2003). "Finding subtle motifs by branching from sample strings". Bioinformatics. 19 Suppl 2: ii149–55. doi:10.1093/bioinformatics/btg1072. PMID 14534184.
↑ Hertz, G. Z.; Stormo, G. D. (1999). "Identifying DNA and protein patterns with statistically significant alignments of multiple sequences". Bioinformatics. 15 (7–8): 563–77. doi:10.1093/bioinformatics/15.7.563. PMID 10487864.
↑ Pavesi, G.; Zambelli, F.; Pesole, G (July 2003). "WeederH: an algorithm for finding conserved regulatory motifs and regions in homologous sequences". Bioinformatics. 19 Suppl 2. doi:10.1093/nar/gkg618. PMID 12824371.
↑ Pavesi, G.; Zambelli, F.; Pesole, G (October 2003). "WeederH: an algorithm for finding conserved regulatory motifs and regions in homologous sequences". Bioinformatics. 19 Suppl 2. doi:10.1186/1471-2105-8-46. PMID 17286865.

پیوند به بیرون

Rajasekaran, S.; Dinh, H. "PMS Motif Search". University of Connecticut. Archived from the original on 2011-05-15.
Rajasekaran, S.; Dinh, H. "Panoptic Motif Search". University of Connecticut. Archived from the original on 2011-08-02.

[Keich_2002-1] ۱٫۰ ^۱٫۱ Keich, U.; Pevzner, P. A. (October 2002). "Finding motifs in the twilight zone". Bioinformatics. 18 (10): 1374–1381. doi:10.1093/bioinformatics/18.10.1374. PMID 12376382.

[Buhler_2001-2] Buhler, J.; Tompa, M. (2002). "Finding motifs using random projections". J. Comput. Biol. 9 (2): 225–242. CiteSeerX 10.1.1.26.2491. doi:10.1089/10665270252935430. PMID 12015879.

[Price_2003-3] ۳٫۰ ^۳٫۱ Price, A.; Ramabhadran, S.; Pevzner, P. A. (October 2003). "Finding subtle motifs by branching from sample strings". Bioinformatics. 19 Suppl 2: ii149–55. doi:10.1093/bioinformatics/btg1072. PMID 14534184.

[Hertz1999-4] Hertz, G. Z.; Stormo, G. D. (1999). "Identifying DNA and protein patterns with statistically significant alignments of multiple sequences". Bioinformatics. 15 (7–8): 563–77. doi:10.1093/bioinformatics/15.7.563. PMID 10487864.

[Nucleic_Acids_Res._2003-5] Pavesi, G.; Zambelli, F.; Pesole, G (July 2003). "WeederH: an algorithm for finding conserved regulatory motifs and regions in homologous sequences". Bioinformatics. 19 Suppl 2. doi:10.1093/nar/gkg618. PMID 12824371.

[Pavesi_2007-6] Pavesi, G.; Zambelli, F.; Pesole, G (October 2003). "WeederH: an algorithm for finding conserved regulatory motifs and regions in homologous sequences". Bioinformatics. 19 Suppl 2. doi:10.1186/1471-2105-8-46. PMID 17286865.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]