Friday, February 24, 2012

FPGA Implementation of Biological Sequence Alignment Algorithm - Introduction


Biological Sequence Alignment Implemented using FPGA - Needleman_Wunsch Algorithm

Biological sequences like DNA and proteins show complex patterns of similarity to one another. In this regard, they mirror the external morphologies of the organisms in which they reside. You'll notice that birds, for example, show natural groupings. You don't have to be a biologist to see that ducks, geese, and swans comprise a reasonably natural group called the waterfowl, and that the similarities between ducks and geese seem too great to explain by mere coincidence. Biological sequences are no different. After all, the reason why ducks look like ducks and geese look like geese is because of their genes. Many molecular biologists are convinced that understanding sequence evolution is tantamount to understanding evolution itself.

Genetic sequences change over time due to three forces: mutation, natural selection, and genetic drift. By studying the similarity or dissimilarity between the sequences of various organisms, we can gain a deeper insight in to the evolution process. Numerous algorithms have been proposed in this regard, the best known being Needleman-Wunsch, Smith-Waterman and BLAST.

The length of typical Biological sequences is billions of characters. Naturally, the sequence alignment operation between two such sequences will be extremely, time and space consuming. This requirement has spawned several fast heuristic algorithms as well as hardware implementations.

The aim of this project is to implement the Needleman-Wunsch algorithm on FPGA. For Needleman-Wunsch algorithm, we use the Parallel Prefix method to reduce the dependencies between the calculations of adjacent cells of the matrix.

No comments:

Post a Comment