Publication detail

Hardware Acceleration of Approximate Tandem Repeat Detection

MARTÍNEK, T. LEXA, M.

Original Title

Hardware Acceleration of Approximate Tandem Repeat Detection

English Title

Hardware Acceleration of Approximate Tandem Repeat Detection

Type

conference paper

Language

en

Original 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.

English 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.

Keywords

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

RIV year

2010

Released

02.05.2010

Publisher

IEEE Computer Society

Location

Charlotte

ISBN

978-0-7695-4056-6

Book

IEEE Symposium on Field-Programmable Custom Computing Machines

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

79

Pages to

86

Pages count

8

URL

BibTex


@inproceedings{BUT34650,
  author="Tomáš {Martínek} and Matej {Lexa}",
  title="Hardware Acceleration of Approximate Tandem Repeat Detection",
  annote="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.",
  address="IEEE Computer Society",
  booktitle="IEEE Symposium on Field-Programmable Custom Computing Machines",
  chapter="34650",
  doi="10.1109/FCCM.2010.21",
  edition="NEUVEDEN",
  howpublished="online",
  institution="IEEE Computer Society",
  year="2010",
  month="may",
  pages="79--86",
  publisher="IEEE Computer Society",
  type="conference paper"
}