Publication Details

Hardware Acceleration of Approximate Tandem Repeat Detection

MARTÍNEK Tomáš and LEXA Matej. Hardware Acceleration of Approximate Tandem Repeat Detection. In: IEEE Symposium on Field-Programmable Custom Computing Machines. Charlotte: IEEE Computer Society, 2010, pp. 79-86. ISBN 978-0-7695-4056-6.
Czech title
Hardwarová akcelerace algoritmů pro hledání přibližných tandemových opakování
Type
conference paper
Language
english
Authors
Martínek Tomáš, doc. Ing., Ph.D. (DCSY FIT BUT)
Lexa Matej, Ing., Ph.D. (FI MUNI)
Keywords

Approximate tandem repeat; dynamic programming; systolic array; FPGA; DNA;

Abstract

Understanding the structure and function of DNA sequences represents an important area of research in modern biology. Unfortunately, analysis of  such data is often complicated by the presence of mutations introduced by evolutionary processes. At the lowest scale, these usually occur in biological sequences as character substitutions, insertions or deletions (indel).  They increase the time-complexity of algorithms for sequence analysis by introducing an element of uncertainty, complicating their practical usage.  One class of such algorithms has been designed to search for tandem repeats with possible errors - approximate tandem repeats. This paper investigates the possibilities for hardware acceleration of approximate tandem repeat searching and describes a parametrized architecture suitable for chips with FPGA technology. The proposed architecture is able to detect tandems with both types of errors (mismatches and indels) and does not limit the length of detected tandem.  A prototype of the circuit was implemented in VHDL language and synthesized for Virtex5 technology. Application on test sequences shows that the circuit is able to speed up tandem searching in orders of thousands in comparison with the best-known software method relying on suffix arrays.

Published
2010
Pages
79-86
Proceedings
IEEE Symposium on Field-Programmable Custom Computing Machines
Conference
The 18th Annual International IEEE Symposium on Field-Programmable Custom Computing Machines, Charlotte, North Carolina, US
ISBN
978-0-7695-4056-6
Publisher
IEEE Computer Society
Place
Charlotte, US
DOI
BibTeX
@INPROCEEDINGS{FITPUB9221,
   author = "Tom\'{a}\v{s} Mart\'{i}nek and Matej Lexa",
   title = "Hardware Acceleration of Approximate Tandem Repeat Detection",
   pages = "79--86",
   booktitle = "IEEE Symposium on Field-Programmable Custom Computing Machines",
   year = 2010,
   location = "Charlotte, US",
   publisher = "IEEE Computer Society",
   ISBN = "978-0-7695-4056-6",
   doi = "10.1109/FCCM.2010.21",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9221"
}
Files
Back to top