Evaluation of Biological Sequence Similarity Using FPGA Technology

Approximate string matching, approximate palindrome detection, approximate tandem repeat detection, systolic array, programmable hardware, FPGA technology, nested loops mapping, design space exploration, high-level synthesis

Understanding structure and function of DNA sequences represents one of the most important goals in area of modern biology research. However, algorithms for DNA analysis are usually complicated by mutations caused by an evolution process, which are usually occurred in form of character
insertion, deletion and substitution.  With respect to these defects the time complexity of the algorithms grows and limits their practical usage.
Techniques for an acceleration of the key operations using specific circuits bring a certain expectation into this area.  The designed circuits are able to achieve the speedup in orders of thousands in comparison to the most powerful conventional processors.  Despite of huge performance of these circuits they are not used in wide range of real word applications.  The main reason lies in often variability of input tasks that leads to change of architecture sizes with respect to the target platform properties. These modifications usually require an intervention of experienced designer and thus complicate their practical usage.  The objective of this thesis is therefore dedicated to design and implementation of novel methods for automated mapping of circuits into the chips with FPGA technology.  At first the problem of mapping is investigated into the detail and formally defined. Based on the formal model a novel mapping technique is designed.  In comparison to the previous approaches, this technique is capable to find the optimal sizes of the resulting circuit and it does not limit description of the architecture parts to linear functions only.