Detail publikace

Hardware Acceleration of Approximate Palindromes Searching

Originální název

Hardware Acceleration of Approximate Palindromes Searching

Anglický název

Hardware Acceleration of Approximate Palindromes Searching

Jazyk

en

Originální abstrakt

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. 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 palindromes with possible errors---approximate palindromes. The best state-of-the-art methods implemented in software show time-complexity between linear and quadratic, depending on required input parameters. This paper investigates the possibilities for hardware acceleration of approximate palindrome searching and describes a parametrized architecture suitable for chips with FPGA technology. A prototype of the proposed architecture was implemented in VHDL language and synthesized for Virtex technology. Application on test sequences shows that the circuit is able to speed up palindrome searching by up to 8000x in comparison with the best-known software method relying on suffix arrays.

Anglický abstrakt

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. 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 palindromes with possible errors---approximate palindromes. The best state-of-the-art methods implemented in software show time-complexity between linear and quadratic, depending on required input parameters. This paper investigates the possibilities for hardware acceleration of approximate palindrome searching and describes a parametrized architecture suitable for chips with FPGA technology. A prototype of the proposed architecture was implemented in VHDL language and synthesized for Virtex technology. Application on test sequences shows that the circuit is able to speed up palindrome searching by up to 8000x in comparison with the best-known software method relying on suffix arrays.

BibTex


@inproceedings{BUT33438,
  author="Tomáš {Martínek} and Matej {Lexa}",
  title="Hardware Acceleration of Approximate Palindromes Searching",
  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.
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 palindromes with
possible errors---approximate palindromes. The best state-of-the-art methods
implemented in software show time-complexity between linear and quadratic,
depending on required input parameters. This paper investigates the possibilities
for hardware acceleration of approximate palindrome searching and describes
a parametrized architecture suitable for chips with FPGA technology. A prototype
of the proposed architecture was implemented in VHDL language and synthesized for
Virtex technology. Application on test sequences shows that the circuit is able
to speed up palindrome searching by up to 8000x in comparison with the best-known
software method relying on suffix arrays.",
  address="IEEE Computer Society",
  booktitle="The International Conference on Field-Programmable Technology",
  chapter="33438",
  doi="10.1109/FPT.2008.4762367",
  edition="NEUVEDEN",
  howpublished="online",
  institution="IEEE Computer Society",
  year="2008",
  month="december",
  pages="65--72",
  publisher="IEEE Computer Society",
  type="conference paper"
}