اراﯾﻪ ﯾﮏ روش ﺟﺪﯾﺪ اﻧﻄﺒﺎق ﭼﻨﺪﮔﺎﻧﻪ ﺗﻮاﻟﯽﻫﺎي دياناي و ﭘﺮوﺗﺌﯿﻦ ﺑﺮاﺳﺎس اﻟﮕﻮرﯾﺘﻢﻫﺎي ﺗﮑﺎﻣﻠﯽ

A New Multiple DNA and Protein Sequences Alignment Method based on Evolutionary Algorithms

مطالعه حيات و آشكارسازي وظايف ژن‌ها يك مسأله مهم در محاسبات زيستي است. در انطباق توالي‌هاي زيستي، براي شناسايي ژن‌ها، اندازه‌گيري شباهت بين توالي‌ها انجام مي‌شود. وقتي با مسأله اندازه ژنوم در انطباق‌هاي چندگانه مواجه مي‌شويم، با مشكل كمبود حافظه و افزايش زمان روبه‌رو هستيم. بنابراين، روشي كه بتواند سريع و بدون كاهش دقت، انطباق ژنوم‌ها را داشته باشد، تأثير به‌سزايي در تحليل توالي‌ها خصوصاً توالي‌هاي بلند را همراه دارد. مواد و روش‌ها: ابتدا روشي را براي تقسيم هر توالي به زير توالي‌هاي كوتاه معرفي مي‌كنيم. سپس از الگوريتم‌هاي تكاملي براي انطباق زير‌توالي‌ها استفاده مي‌كنيم. نتايج: روش پيشنهادي در هفت مجموعه داده با تعداد نكلوئتيدهاي مختلف به‌ازاي هر توالي دي‌ان‌اي و افزايش تدريجي از 18000 تا 14 ميليون نكلئوتيد، ارزيابي شده و با پنج روش مشهور انطباق چندگانه مقايسه شده است. بالاترين ميزان دقت براي باكتري variola با ميزان 0/93 و بالاترين سرعت انطباق 0/6 بر حسب دقيقه براي اين باكتري است. نتيجه‌گيري: اكثر روش‌هاي انطباق چندگانه در توالي‌هاي كوتاه يا تعداد كم، دقت مناسبي دارند اما براي دنباله‌هاي طولاني‌تر به قدرت محاسباتي بالايي نياز دارند. الگوريتم پيشنهادي با انطباق توالي‌هاي بلند، در زماني قابل قبول و حفظ دقت و همچنين استفاده بهينه از حافظه، بر اين نقص غلبه مي‌كند.

The study of life and the detection of gene functions is an important issue in biological science. Multiple sequences alignment methods measure the similarity of DNA sequences. Nonetheless, when the size of genome sequences is increased, we encounter with the lack of memory and increasing the run time. Therefore, a fast method with a suitable accuracy for genome alignment has a significant impact on the analysis of long sequences. Methods: We introduce a new method in which, it first divides each sequence into short sequences. Then, it uses evolutionary algorithms to align the sequences. Results: The proposed method has been evaluated in seven datasets with different number of nucleotides per DNA sequence (18,000 to 14 million) and compared to five popular multiple sequences alignment methods. The highest accuracy for the variola bacterium dataset is 93% and the highest alignment rate is 0.6 per minute for this bacterium. Conclusion: Most multiple alignment methods in short sequences or datasets with only a few sequences have good accuracy while require high computational time for longer sequences. The proposed algorithm overcomes this drawback by aligning long sequences in an acceptable time and maintaining accuracy as well as optimal memory usage.