Detail publikace
Hardware Acceleration of Approximate Palindromes Searching
Lexa Matej, Ing., Ph.D. (UPSY FIT VUT)
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{FITPUB8780, author = "Tom\'{a}\v{s} Mart\'{i}nek and Matej Lexa", title = "Hardware Acceleration of Approximate Palindromes Searching", pages = "65--72", booktitle = "The International Conference on Field-Programmable Technology", year = 2008, location = "Taipei, TW", publisher = "IEEE Computer Society", ISBN = "978-1-4244-2796-3", doi = "10.1109/FPT.2008.4762367", language = "english", url = "https://www.fit.vut.cz/research/publication/8780" }