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

Binary integer programming for multiple sequence alignment

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

In the last decades, advances in molecular biology have led to a rapid increase in sequencing of species of organisms and sequence alignment is usually the first step in understanding the molecular function of a sequence. This is accomplished by aligning the unknown sequence with one or more evolution-based sequences. The optimal alignment adjusts two or more sequences to match the maximum number of identity or similar residue. Two types of sequence alignments are: Pairwise SA (PSA) and Multiple SA (MSA). The advantage of MSA is more than the PSA, because several members of a family of sequences take into account and thus provide more biological information. For PSA, dynamic programming (DP) provides the optimal solution, but uses DP in MSA increases complexity, and so the usual MSA routines are heuristic or approximate. These methods include Progressive alignment, Iterative approach, hidden Markov model, and meta-heuristic algorithm. In this paper, the mathematical model for MSA is presented which can be used as the basis for optimal solution in different methods. To do this, used a intermediate matrix of zero and one (X), to model a sequence. To obtain the results, the model implemented with the genetic algorithm in web-based and the results show success in MSA