Detail publikace
Hardware Acceleration of Approximate Palindromes Searching
Approximate palindromes, systolic array, FPGA technology
Porozumnění struktury a funkce DNA sekvencí je jednou z nejdůležitějších oblastí výzkumu moderní biologie. Bohužel analýza těchto dat je často komplikována mutacemi vzniklými v rámci evolučního procesu. Tyto změny zvyšují časovou složitost algoritmů pro analýzu sekvencí a komplikují jejich praktickou využitelnost. Jednou z tříd takových algoritmů tvoří hledání palindromatických struktur s možnými chybami - přibližných palindromů. Nejlepší současné algoritmy implementované v software vykazují časovou složitost někde mezi lineární a kvadratickou v závislosti na vstupních parametrech. Tento článek zkoumá možnosti hardwarové akcelerace pro hledání přibližných palindromů a ukazuje parametrizovatelnou architekturu vhodnou prou čipy s FPGA technologií. Prototym této architektury byl implementován v jazyce VHDL a syntetizován pro technologii Virtex. Ohodnocení obvodu na testovacích sekvencích ukazuje zrychlení až 8000x ve srovnání s nejlepší známou softwarovou metodou založenou na suffixových polých.
@inproceedings{BUT33438,
author="Tomáš {Martínek} and Matej {Lexa}",
title="Hardware Acceleration of Approximate Palindromes Searching",
booktitle="The International Conference on Field-Programmable Technology",
year="2008",
pages="65--72",
publisher="IEEE Computer Society",
address="Taipei",
doi="10.1109/FPT.2008.4762367",
isbn="978-1-4244-2796-3",
url="https://www.fit.vut.cz/research/publication/8780/"
}