برنامه ریزی عدد صحیح باینری برای همترازی توالی چندگانه

در چند دهه اخیر، پیشرفت در زیست شناسی مولکولی باعث افزایش سریع تعیین توالی ژنوم گونه های موجودات شده است و همترازی توالی معمولا اولین گام برای درک عملکرد مولکولی یک توالی است. این کار با همترازی توالی ناشناخته با یک یا چند توالی شناخته شده بر مبنای تکامل انجام می شود. هم ترازی مطلوب، دو یا چند توالی را به گونه ای تنظیم می کند که حداکثر تعداد عناصر یکسان یا مشابه را با هم مقایسه کند. دو نوع همترازی توالی ترتیب عبارتند از: توازن جفتی (PSA) و همترازی توالی چندگانه (MSA). فواید MSA بیشتر از PSA است، زیرا چندین عضو یک خانواده توالی را در نظر می گیرد و در نتیجه اطلاعات بیولوژیکی بیشتری ارائه می دهد. برای PSA، برنامه ریزی پویا (DP) راه حل بهینه را ارائه می کند اما در MSA در صورت استفاده از DP، پیچیدگی افزایش می یابد و بنابراین روش های معمول MSA به صورت اکتشافی یا تقریبی است. این روش ها شامل همترازی جلورونده، روش های تکراری، مدل مارکوف پنهان و الگورتیم های متاهیورستیک می باشد. در این مقاله مدل ریاضی برای MSA ارائه شده است که می تواند به عنوان پایه حل بهینه در روش های مختلف قرار گیرد. برای اینکار از یک ماتریس واسطه X که عناصر آن باینری است برای مدل سازی توالی استفاده شده است. برای بدست آوردن نتایج، مدل با روش حل الگوریتم ژنتیک به صورت تحت وب پیاده سازی شده است و نتایج بدست آمده حاکی از موفقیت همترازی توالی چندگانه می باشد.

Keywords:

همترازی توالی چندگانه , مدل سازی ریاضی , بیوانفورماتیک , برنامه ریزی عدد صحیح