بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تطبیق دنباله هاي DNA با استفاده از الگوریتم ژنتیک
چکیده
تطبیق دنباله ها یکی از مسائل مهم در زمینه تحلیل هاي زیستی می باشد که می تواند به صورت سراسري یا محلی صورت گیرد و براي این منظور می توان از روش هاي مختلفی همچون برنامه نویسی پویا و الگوریتم ژنتیک استفاده کرد. در روش برنامه نویسی پویا با افزایش تعداد دنباله ها براي تطبیق، هزینه محاسبات و پیچیدگی زمانی و مکانی به صورت نمایی افزایش می یابد به همین دلیل یکی از روش هایی که اخراًی به منظور تطبیق دنباله ها توسعه داده شده است، الگوریتم ژنتیک می باشد. در این مقاله، تطبیق سراسري دنباله هاي DNA با استفاده از الگوریتم ژنتیک مطرح شده است و بر این اساس یک الگوریتم پیشنهادي ارائه شده که قابلیت توسعه براي تطبیق چندین دنباله را دارد. با تطبیق دنباله ها می توان میزان شباهت آن ها و نواحی همسان و غیر همسان را شناسایی کرد. نتایج حاصل از تطبیق می تواند در زمینه هاي مختلف علوم ژنتیک همچون تشخیص سلول هاي سالم از سلول هاي سرطانی، تشخیص رنگ چشم و ... استفاده شود. نتایج تجربی بدست آمده نشان می دهد، روش پیشنهادي نسبت به روش GAPSA قادر به یافتن تطبیق هاي بیشتري می باشد.
واژه هاي کلیدي : الگوریتم ژنتیک، برنامه نویسی پویا، بیوانفورماتیک، تطبیق دنباله.
۱- مقدمه
مطالعه پدیده هاي زیستی چندین سال است که به وسیله دانشمندان مختلف بررسی می شود و در چند دهه اخیر این مطالعات با سرعت بیشتري در حال انجام است. پیشرفت هاي زیست مولکولی در چند دهه گذشته، شناسایی دنباله هاي1
زیادي از ژنوم هاي2 موجودات مختلف را ممکن کرده است و باعث ایجاد شاخه جدیدي از علم زیست شناسی بـه نـام بیوانفورماتیک3 شده است که به ذخیره، تجزیه، تحلیل و تفسیر اطلاعات آزمایشگاهی همچون داده هاي زیستی، دنبالـه اسیدهاي نوکلئیک4 و دنباله هاي پروتئین5 و اطلاعات ساختاري می پردازد.
دنباله هاي مولکولی6DNA، 7RNA و پروتئین متشکل از چندین عنصر مـی باشـند. دنبالـه هـاي DNA، RNA از 4
نوع نماد اصلی و پروتئین ها از 20 نوع نماد تشکیل شده اندDNA .[1] واحد اصلی یـک ارگانیسـم مـی باشـد و دنبالـه هاي آن از نمادهايA}، T، C، {Gتشکیل شده است. طول دنباله هاي DNA در انواع مختلف، از چند صـد بـه چنـدین بیلیون می رسد. بنابراین پیدا کردن میزان شباهت یا تفاوت بین دنباله هاي DNA کار بسیار مشکلی می باشد3]،2،. [1
در بخش2 این مقاله، مفاهیم اساسی همچون تطبیق دنباله ها8 و انـواع آن بیـان شـده اسـت. در بخـش 3 روش هـاي پرکاربرد جهت تطبیق دنباله ها و در بخش4 روش پیشنهادي بر اساس الگـوریتم ژنتیـک ارائـه شـده اسـت. بخـش5 نیـز شامل نتایج تجربی و مشاهدات می باشد.
-2 تطبیق دنباله ها
تطبیق دنباله ها یکی از مهمترین فعالیت هاي تحلیلی در بیوانفورماتیک است که در آن دو یـا چنـد دنبالـه بـا هـم مقایسه می شوند تا از این طریق شباهت ها و تفاوت هاي موجود در بین آن ها شناسـایی شـود. وجـود تشـابه بـین دنبالـه هاي DNA را می توان چنین توجیه کرد که این دنباله هـا داراي جـد مشـترکی هسـتند کـه بـه واسـطه جهـش در طـول تکامل، تغییراتی در دنباله هاي آن ها ایجاد شده است.[4]
هدف از تطبیق دو دنبالهاحتمالاً( با اندازه هاي مختلف) نوشتن ردیفی آن ها و تفکیـک دنبالـه هـا بـه قسـمت هـاي کوچکتر از طریق قرار دادن فضاهاي خالی9 در محل هاي مختلفی در طول دنباله می باشد، تا بدین وسیله زیر دنباله هاي همسان بیشتري، براساس رابطه یک به یک تطبیق داده شوند.[ 4]
نتایج حاصل از تطبیق دنباله ها در زمینه هاي مختلف علوم زیست شناسی و ژنتیک مورد استفاده قرار می گیرند.
در ادامه انواع تطبیق هاي موجود و قابل اعمال بر روي دنباله ها بیان شده است.
1-2 تطبیق سراسري10
با استفاده از این تطبیق تلاش شده به این سوال زیستی در دنیاي واقعی پاسـخ داده شـود کـه "چقـدر بـین دو دنبالـه
شباهت وجود دارد؟". در این تطبیق همه کاراکترهاي دو دنباله در فرآیند شـرکت کـرده و هـدف پیـدا کـردن بهتـرین سازگاري در کل دو دنباله می باشد5]،4،.[ 2
تطبیق سراسري دو دنباله زیر در شکل 1 ارائه شده است.
X='TCCCAGTTATGTCAGGGGACACGAGCATGCAGAGAC'
Y='AATTGCCGCCGTCGTTTTCAGCAGTTATGTCAGATC'
شکل:1 تطبیق سراسري دو دنباله .[ 5 ] DNA
در شکل1، 21 حالت سازگاري(تطابق)، 2 حالت ناسازگاري و 24 عدد فضاي خالی وجـود دارد کـه بـه ترتیـب بـا استفاده از میله هاي عمودي((|،خط چین((¦ و خط تیره(-) نشان داده شده است.
2-2 تطبیق محلی11
با استفاده از این تطبیق تلاش شده به این سوال زیستی در دنیاي واقعی پاسخ داده شود که "کـدام نـواحی در دنبالـه هاي مختلف، داراي ژن هاي یکسانی هستند؟". با استفاده از تطبیق سراسري نمی توان نواحی مشابه را در بین دنباله هاي مختلف پیدا کرد، زیرا تلاش می کند تطبیق را بر روي کل دنباله اعمال کند.[ 5 ]
اگر دو دنباله با یکدیگر تشابه کلی نداشته باشند و فقط در برخی نواحی، تشابه زیادي در بـین آن هـا وجـود داشـته باشد، از طریق تطبیق محلی می توان این نواحی را مشخص کرد. در شکل2، تطبیق محلـی دو دنبالـه X و Y نشـان داده شده است.
شکل:2 تطبیق محلی دو دنباله .[ 5 ] DNA
در صورتی که عمل تطبیق بر روي دو دنباله اعمال شود، تطبیق جفتی دنباله ها12 و در صورتی که بـر روي چنـدین دنباله اعمال شود، تطبیق چندگانه دنباله ها13 نامیده می شود.
-3 روش هاي پیاده سازي تطبیق دنباله ها
برنامه نویسی پویا14 و الگوریتم ژنتیک15 از روش هاي اصلی و پرکاربرد جهت تطبیق دنباله هـا مـی باشـند. در سـال هاي اخیر، روش ها و الگوریتم هاي مختلفی براي تطبیق دنباله ها بر اساس برنامه نویسی پویا و الگوریتم ژنتیـک مطـرح شده است13]،12،11،10،9،8،7،.[ 6 به عنوان مثال Isokawa et al با استفاده از الگـوریتم ژنتیـک روشـی بـراي تطبیـق دنباله هاي چندگانه ارائه کرده است.[7] همچنین Notredame et al با اسـتفاده از الگـوریتم ژنتیـک روش SAGA را جهت تطبیق دنباله ها بیان کرده است.[10]
1-3 برنامه نویسی پویا
برنامه نویسی پویا کاربرد وسیعی در بهینه سازي مسائل دارد و از طریق محاسبات ریاضی، دست یافتن به تطبیق بهینه دنباله ها را تضمین می کند15]،14،. [1 این روش اغلب براي تطبیق جفتی دنباله ها مورد استفاده قرار می گیرد، زیرا در
تطبیق چندگانه دنباله ها پیچیدگی الگوریتم به صورت نمایی افزایش می یابد.[16]
الگوریتمی که اغلب به منظور تطبیق سراسـري دنبالـه هـا مـورد اسـتفاده قـرار مـی گیـرد، الگـوریتم
Wunsch می باشد که نمونه اي از برنامه نویسی پویا است و در تطبیق دو دنبالـه بـا طـول هـاي n و m داراي پیچیـدگی
زمانی و مکانی O(mn) می باشد.[17] برنامه نویسی پویا یک روال بازگشتی می باشد که مسئله را به چندین زیـر مسـئله تقسیم می کند و در آن جواب هر مرحله، تابعی از زیر مسئله قبلی می باشد و به همسایه هاي بلافصل آن بستگی دارد.
برنامه نویسی پویا در تطبیق جفتی دنباله ها، بررسی را از انتهاي دو دنباله شروع کرده و تلاش مـی کنـد آنهـا را بـر اساس طرح امتیازگذاري سازگاري، ناسازگاري و فضاي خالی تطبیق دهد و یک ماتریس امتیازگذاري ایجاد کنـد کـه در آن بالاترین امتیاز، نشان دهندة تطبیق بهینه باشد.
ماتریس امتیازگذاري، ماتریسی با ابعاد n و m است که n و m طول دو دنباله می باشند. این ماتریس براساس رابطـه
(1) و به صورت بازگشتی ایجاد می شود.[18]
مقدار تابع F(i,j) بالاترین امتیاز براي موقعیت i در دنباله X و موقعیت j در دنباله Y می باشد. d هزینه جریمه فضاي خالی16 و s امتیاز سازگاري/ ناسازگاري بین Xi و Yj مـی باشـد. در ابتـدا، در موقعیـت F(0,0) مـاتریس امتیازگـذاري، مقدار 0 در نظر گرفته می شود.[18]
در این زمینه برنامه هاي مختلفی با قابلیت تطبیق بهینه دنباله ها ارائه شده است.[19]
به عنوان مثال براي تطبیق سراسـري دو دنبالـه X='ACCAGA' و Y='ACTCATA' بـا در نظـر گـرفتن رابطـه((2،
ماتریس امتیازگذاري شکل3، ایجاد شده است.[3]
شکل:3 ماتریس امتیازگذاري تطبیق سراسري دو دنباله .[3 ] DNA
سپس از مکان سمت راست و پایین ماتریس، فلش ها دنبال می شوند تا تطبیق زیر حاصل شود:
A C T C A C A
A C C A C A
الگوریتمی که اغلب براي تطبیق محلی دنباله ها مورد اسـتفاده قـرار مـی گیـرد، الگـوریتم Smith-Waterman مـی باشد که نمونه تغییر یافته الگوریتم Needleman-Wunsch است.[20]
برنامه نویسی پویا را نمی توان از تطبیق جفتی به حالت تطبیق چندگانه تعمیم داد زیرا هزینه محاسـبات و پیچیـدگی زمانی و مکانی آن به صورت نمایی افزایش می یابد. بنابراین از روش هاي دیگري همچون الگوریتم ژنتیک بـه منظـور تطبیق دنباله ها استفاده شده است. [2 ]
2-3 الگوریتم ژنتیک
الگوریتم ژنتیک یک روش بهینه سازي و اتفاقی می باشد که در سال هاي اولیه دهـه 1970 توسـط John Holland
ارائه شده است و از تکنیک مهندسی معکوس براي رسیدن به نتیجه مورد نظر استفاده مـی کنـد22]،21،.[23 ایـن روش براي حل مسائل بهینه سازي ترکیبی که روش هاي سنتی در حل کارآمد آن با شکست مواجه شده اند، مفید می باشد و راه حل هاي بهینه یا نزدیک به بهینه را پیدا می کند.
مزیت اصلی الگوریتم ژنتیک نسبت به روش هاي بهینه سازي دیگر این است که نیازي به الگـوریتم خاصـی جهـت حل یک مسئله معین ندارد و فقط نیازمند یک تابع برازش، براي ارزیابی کیفیـت راه حـل هـاي مختلـف مـی باشـد.[2]
الگوریتم ژنتیک در زمینه تطبیق جفتی و تطبیق چندگانه دنباله ها به کار می رود27]،26،25،24،. [15
الگوریتم ارائه شده توسط Othman et al به نام GAPSA یکی از روش هاي تطبیق جفتـی دنبالـه هـا بـا اسـتفاده از الگوریتم ژنتیک می باشدکه بر خلاف روش برنامه نویسی پویا، قابلیت توسعه از حالت تطبیق جفتی به تطبیـق چندگانـه دنباله ها را دارد.
فرض کنید دو دنباله R و Q با طول هاي n و m براي تطبیق دادن، موجود هسـتند کـه شـامل عناصـري از مجموعـه الفباي تعریف شدة DNA می باشند. در این الگوریتم بعد از تعیین تعداد جمعیـت اولیـه، انتخـاب جمعیـت اولیـه بـه دو صورت زیر امکان پذیر می باشد:
: Pure Random • در این روش با قرار گرفتن فضاهاي خالی به صـورت تصـادفی، در بـین عناصـر دنبالـه هاي داده شده براي تطبیق، جمعیت اولیه (ماتریس هاي RT و (QT ایجاد می شود.
: Enhanced • در این حالت سطرهاي ماتریس تطبیق RT) و (QT، به تعدادي ناحیه تقسیم می شـود. سـپس نواحی به صورت تصادفی انتخاب شده و فضاهاي خالی به صورت تصادفی در این نواحی قرار می گیرند.
در هر دو حالت باید کنترل شود که طول دنباله ها در جمعیت اولیه، از مجموع طـول دو دنبالـه اولیـه بیشـتر نشـود و فضاهاي خالی در مکان هاي یکسانی در دو دنباله متناظر قرار نگیرند. در الگوریتم پیشـنهادي از روش Pure Random
با اعمالی یکسري تغییرات استفاده شده است.
پس از تولید جمعیت اولیه، تـابع برازشـی بـراي محاسـبه میـزان شـباهت راه حـل هـا انتخـاب مـی شـود و بـا اعمـال عملگرهاي انتخاب17 ، ادغام18 و جهش19 بر روي راه حل هاي جمعیت اولیه با بهترین میزان برازش، مـی تـوان جمعیـت نسل بعد را بدست آورد.
با استفاده از عملگر انتخاب، می توان بخشی از جمعیت نسل بعد را، از طریق انتخاب راه حل هایی از جمعیت اولیـه با بالاترین میزان برازش، در نظر گرفت.
با استفاده از عملگر ادغام، دو سطر از ماتریس هاي جمعیت اولیه RT و QT با بـالاترین میـزان بـرازش انتخـاب مـی شود. سپس دو سطر ماتریس RT، تعویض می شود و دو سطر ماتریسQT بدون تغییر باقی می ماند و به عنـوان بخشـی از جمعیت نسل بعد در نظر گرفته می شود و یا بالعکس.
