International Conference on Computer and Knowledge Engineering

Home / 11th International Conference on Computer and Knowledge Engineering

Divide and Conquer Approach to Long Genomic Sequence Alignment

Authors :

Mahmoud Naghibzadeh¹ Samira Babaei² Behshid Behkmal³ Mojtaba Hatami⁴

1- Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran 2- Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran 3- Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran 4- Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran

Keywords :

genome sequence alignment, divide and conquer, longest common subsequence, big genome data

Abstract :

optimal alignment of DNA sequences is a reliable approach to discover mutations in one sequence in comparison to the other or to discover the differences between two sequences. Needleman-Wunsch is the most applicable software for optimal alignment of the sequences and Smith-Waterman is the most applicable one for local optimal alignment. Their performances are excellent with short sequences, but as the sequences become longer their performance degeneration grow exponentially to the point that it is practically impossible to align two compete human DNAs. Alignment process is essential in diagnosis of genome related diseases. Therefore, many researches are done or being conducted to find ways of performing the alignment with tolerable time and memory consumptions. One such effort is breaking the sequences into same number of parts and align corresponding parts together to produce the overall alignment. With this, there are three achievements simultaneously: run time reduction, main memory utilization reduction, and the possibility to better utilize multiprocessors, multicores and General Purpose Graphic Processing Units (GPGPUs). In this research, the method for breaking long sequences into smaller parts is based on the divide and conquer approach. The breaking points are selected along the longest common subsequence of the current sequences. The method is demonstrated to be very efficient with respect to both time and main memory utilization.