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

چکیده مقاله

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

کلیدواژه‌ها

نویسندگان

سید علی لاجوردی

دانشجوی دکتری فناوری اطلاعات، دانشگاه تربیت مدرس؛

مهرداد کارگری

استادیار دانشکده صنایع و سیستم ها، دانشگاه تربیت مدرس؛

لاجوردی، سیدعلی و کارگری، مهرداد،1398،برنامه ریزی عدد صحیح باینری برای همترازی توالی چندگانه،پنجمین کنفرانس بین المللی مهندسی صنایع و سیستم­ها (ICISE ۲۰۱۹)،مشهد

ارائه‌شده در

مجموعه مقالات پنجمین کنفرانس بین المللی مهندسی صنایع و سیستم­ها (ICISE ۲۰۱۹)13 شهریور 1398 · مشهد