ای‌ام چندگانه برای استخراج موتیف

ای‌ام چندگانه برای استخراج موتیف یا به اختصار ام‌ای‌ام‌ای (MEME) ابزاری است ریاضی برای پیدا کردن موتیف در مجموعه‌ای از رشته‌های پروتئین یا دی‌ان‌ای به هم مرتبط.
موتیف یک الگو است که به صورت تکراری در مجموعه‌ای از رشته‌های پروتئین یا دی‌ان‌ای به‌هم‌مرتبط وجود دارد. الگوریتم بیشینه کردن امید ریاضی (ای‌ام، EM) موتیف‌ها را در قالب یک ماتریس نمایش می‌دهد. ماتریسی که موقعیت‌ها را مستقل فرض کرده و درایه‌هایش احتمال وقوع هر حرف (در دی‌ان‌ای اسید نوکلئیک و در پروتئین اسید امینه) در هر موقعیت الگو را نشان می‌دهد. موتیف‌های تکی در ام‌ای‌ام‌ای دارای گپ نیستند و الگوهایی که دارای گپ‌هایی با سایزهای متغیر هستند، توسط ام‌ای‌ام‌ای به دو یا چند موتیف تکی شکسته می‌شوند.
ام‌ای‌ام‌ای مجموعه‌ای از رشته‌های پروتئین یا دی‌ان‌ای را ورودی می‌گیرد و به تعداد خواسته شده موتیف برمیگرداند. این الگوریتم برای پیدا کردن بهترین طول برای موتیف‌ها، تعداد تکرار آنها و شرح هر موتیف از روش‌های آماری استفاده می‌کند.
تعریف
از دو منظر می‌توان عمل الگوریتم ام‌ای‌ام‌ای را بررسی کرد. از دیدگاه زیستی، ام‌ای‌ام‌ای موتیف‌های مشترک در مجموعه‌ای از رشته‌های تراز نشده را تشخیص داده و پیدا می‌کند. از دیدگاه علوم کامپیوتر، ام‌ای‌ام‌ای مجموعه‌ای از زیر رشته‌هایی که تقریبا به هم شباهت داشته و هم پوشانی ندارند را در مجموعه‌ای از رشته‌های ورودی پیدا می‌کند.
کاربرد
به کمک ام‌ای‌ام‌ای می‌توان ساختار و عملکردهای زیستی مشابهی را در رشته‌های متفاوت پیدا کرد. باید توجه داشت که رشته‌های ورودی ممکن است بسیار با هم متفاوت بوده و طول موتیف‌هایی که در آنها پیدا می‌شود بسیار کوتاه باشد. همچنین ممکن است محل چسبیدن پروتئین‌ها بسیار خاص باشد. در واقع برای بهتر پیدا کردن موتیف‌ها از دیدگاه زیستی، می‌توانیم با دقت یکی از پارامترهای زیر را انتخاب کنیم:
بهترین طول برای موتیف
تعداد تکرار موتیف در یک رشته
ترکیب هر موتیف
اجزای الگوریتم
الگوریتم از چند تابع شناخته شده استفاده می‌کند:
الگوریتم بیشینه کردن امید ریاضی
اکتشافی بیشینه کردن امید ریاضی برای انتخاب نقطه شروع بیشینه کردن امید ریاضی
درست نمایی بیشینه
شروع از چندین نقطه برای پیدا کردن موتیف‌ها با سایزهای مختلف
الگوریتم حریصانه برای پیدا کردن موتیف‌های متفاوت
در حالت کلی مشخص نیست موقعیت شروع کجاست. چندین امکان وجود دارد:
هر رشته دقیقا یک موتیف داشته باشد.
هر رشته صفر یا یک موتیف داشته باشد.
هر رشته به هر میزانی موتیف داشته باشد.
مثال
در مثال زیر، ماتریس وزن به ازای 3 رشته متفاوت بدون گپ در اختیار است.
1: C GGGTAAGT
2: A AGGTATGC
3: C AGGTGAGG
حال با شمردن تعداد اسید نوکلئیک‌ها در هر رشته ماتریس زیر شکل می‌گیرد:
A: 1 2 0 0 0 2 2 0 0
7
C: 2 0 0 0 0 0 0 0 1
3
G: 0 1 3 3 0 1 0 3 1
12
T: 0 0 0 0 3 0 1 0 1
5
حال از جمع کل داریم 27 = 5+12+3+7. که با گذاشتن آن در مخرج به احتمال هر اسید نوکلئیک می‌رسیم.
A: 7/27 = 0.26
C: 3/27 = 0.11
G: 12/27 = 0.44
T: 5/27 = 0.19
با تقسیم تک تک درایه‌های ماتریس وزن بر تعداد کل رشته‌ها (در مثال ما ۳) ماتریس وزن را بازنویسی می‌کنیم:
A: 0.33 0.66 0.00 0.00 0.00 0.66 0.66 0.00 0.00
C: 0.66 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.33
G: 0.00 0.33 1.00 1.00 0.00 0.33 0.00 1.00 0.33
T: 0.00 0.00 0.00 0.00 1.00 0.00 0.33 0.00 0.33
سپس درایه‌های ماتریس وزن در موقعیت x i را تقسیم بر احتمال اسید نوکلئیک x می‌کنیم.
A: 1.27 2.30 0.00 0.00 0.00 2.30 2.30 0.00 0.00
C: 6.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 3.00
G: 0.00 0.75 2.27 2.27 0.00 0.75 0.00 2.27 0.75
T: 0.00 0.00 0.00 0.00 5.26 0.00 1.74 0.00 1.74
به طور کلی می‌توان احتمالات را در هم ضرب کرد. در این جا برای هر اسید نوکلئیک یک درایه صفر وجود دارد، به همین دلیل از همه درایه‌ها لگاریتم گرفته و تعریف می‌کنیم log(0)= -10
A: 0.10 0.36 -10 -10 -10 0.36 0.36 -10 -10
C: 0.78 -10 -10 -10 -10 -10 -10 -10 0.48
G: -10 -0.1 0.36 0.36 -10 -0.1 -10 0.36
T: -10 -10 -10 -10 0.72 -10 0.24 -10 0.24
حال ماتریس وزن مورد نیاز در الگوریتم را در اختیار داریم که به کمک آن می‌توان به یک رشته پروموتور امتیاز اختصاص داد. برای این کار باید اعدادی که در موقعیت x i ماتریس هستند را با هم جمع کرد. به طور مثال برای پروموتور AGGCTGATC داریم:
0.10 - 0.1 + 0.36 - 10 + 0.72 - 0.1 + 0.36 - 10 + 0.48 = -18.18
که با تقسیم بر تعداد درایه‌ها (در اینجا 9) به امتیاز نهایی می‌رسیم: -2.02.
معایب
الگوریتم MEME چندین نقطه ضعف دارد از جمله:
درج/جایگزینی/گپ مجاز نیست.
هرگاه موتیف جدیدی پیدا شد داده‌های ورودی را پاک می‌کند (فرض می‌کند موتیف جدید صحیح است).
پیچیدگی زمانی الگوریتم بسیار زیاد است.