Detail publikace

Hardware Acceleration of Approximate Palindromes Searching

MARTÍNEK Tomáš a LEXA Matej. Hardware Acceleration of Approximate Palindromes Searching. In: The International Conference on Field-Programmable Technology. Taipei: IEEE Computer Society, 2008, s. 65-72. ISBN 978-1-4244-2796-3.
Název česky
Hardwarová akcelerace algoritmů pro vyhledávání palindromů na základě podobnosti
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Martínek Tomáš, doc. Ing., Ph.D. (FIT VUT)
Lexa Matej, Ing., Ph.D. (UPSY FIT VUT)
Abstrakt

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.

Rok
2008
Strany
65-72
Sborník
The International Conference on Field-Programmable Technology
Konference
The International Conference on Field-Programmable Technology, Taipei, TW
ISBN
978-1-4244-2796-3
Vydavatel
IEEE Computer Society
Místo
Taipei, TW
DOI
UT WoS
000263224000009
BibTeX
@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"
}
Soubory
Nahoru