PhD. Theses

Martínek, T.: Hodnocení podobnosti biologických sekvencí s využitím technologie FPGA, Brno, CZ, UPSY FIT VUT, 2010, p. 125
Publication language:czech
Original title:Hodnocení podobnosti biologických sekvencí s využitím technologie FPGA
Title (en):Evaluation of biological sequence similarity using FPGA technology
Pages:125
Place:Brno, CZ
Year:2010
Publisher:Department of Computer Systems FIT BUT
Keywords
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
Annotation
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 usually occur 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. This problem becomes more significant in the light of next-generation sequencing technologies, which are able to generate billions of bases per minute at the cost of several hundreds of dollars.  Techniques for an acceleration of the key and frequently used operations using specific circuits bring a certain expectation into this area.  Therefore, the first part of this thesis is dedicated to hardware acceleration of selected algorithms for DNA sequence analysis, especially algorithms for approximate palindrome and approximate tandem repeat detection. In comparison to previous approaches, the novel designed circuits are configurable using several parameters and capable to detect all types of defects (character insertion, deletion and substitution). Mapping of these architectures into the FPGA technology shows speedup in orders of thousands in comparison to the best known algorithms, which are implemented in the software and use suffix array structure. Despite of huge performance of these novel as well as existing circuits, they are not used in wide range of real word applications.  The main reason lies often in variability of input tasks that leads to change of architecture parameters and adaptation of its dimensions with respect to the target platform properties. These modifications usually require an intervention of experienced designer, and thus complicate their usage in real word applications.  The second part 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 using a parametrized architecture model. Based on this formal model, a novel mapping technique is designed. In comparison to previous approaches, this technique is capable to find the optimal dimensions of the resulting circuit and it does not limit description of the architecture parts to linear functions only. Finally, the proposed method is evaluated on three examples of architectures for DNA sequence analysis. The parametric model is build for each example and the method is applied to find the optimal dimensions of the circuits with respect to limited I/O bandwidth and limited amount of resources inside the chip.
BibTeX:
@PHDTHESIS{
   author = {Tomáš Martínek},
   title = {Hodnocení podobnosti biologických sekvencí s využitím
	technologie FPGA},
   pages = {125},
   year = {2010},
   location = {Brno, CZ},
   publisher = {Department of Computer Systems FIT BUT},
   language = {czech},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9414}
}

Your IPv4 address: 54.235.20.17
Switch to IPv6 connection

DNSSEC [dnssec]