Hardware Acceleration of Approximate Tandem Repeat Detection

D 2010

Hardware Acceleration of Approximate Tandem Repeat Detection

MARTÍNEK, Tomáš a Matej LEXA

Základní údaje

Originální název

Hardware Acceleration of Approximate Tandem Repeat Detection

Autoři

MARTÍNEK, Tomáš a Matej LEXA

Vydání

Los Alamitos, CA, USA, 18th IEEE Symposium on Field-Programmable Custom Computing Machines, od s. 79-86, 8 s. 2010

Nakladatel

IEEE Computer Society

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/10:00048631

Organizační jednotka

Fakulta informatiky

ISBN

978-0-7695-4056-6

Klíčová slova česky

FPGA; tandemové opakování; analýza sekvence DNA; systolické pole; dynamické programování

Klíčová slova anglicky

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

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 17. 1. 2013 16:44, doc. Ing. Matej Lexa, Ph.D.

Anotace

ORIG CZ

V originále

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

Česky

Prezentujeme algoritmus pro vyhledavani pribliznych tandemovych opakovani v biologickych sekvencich. Algoritmus je implementovan na FPGA cipech.

Návaznosti

GA204/08/1560, projekt VaV

Název: Bioinformatická a experimentální identifikace nekanonických struktur v genomové DNA

Investor: Grantová agentura ČR, Bioinformatická a experimentální identifikace nekanonických struktur v genomové DNA

Citovat

MARTÍNEK, Tomáš a Matej LEXA. Hardware Acceleration of Approximate Tandem Repeat Detection. In 18th IEEE Symposium on Field-Programmable Custom Computing Machines. Los Alamitos, CA, USA: IEEE Computer Society, 2010, s. 79-86. ISBN 978-0-7695-4056-6.

@inproceedings{881398,
   author = {Martínek, Tomáš and Lexa, Matej},
   address = {Los Alamitos, CA, USA},
   booktitle = {18th IEEE Symposium on Field-Programmable Custom Computing Machines},
   keywords = {Approximate tandem repeat; dynamic programming; systolic array; FPGA; DNA;},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Los Alamitos, CA, USA},
   isbn = {978-0-7695-4056-6},
   note = {This paper received the FCCB 2010 Best Paper Award},
   pages = {79-86},
   publisher = {IEEE Computer Society},
   title = {Hardware Acceleration of Approximate Tandem Repeat Detection},
   year = {2010}
}

TY  - CONF
ID  - 881398
AU  - Martínek, Tomáš - Lexa, Matej
PY  - 2010
TI  - Hardware Acceleration of Approximate Tandem Repeat Detection
PB  - IEEE Computer Society
CY  - Los Alamitos, CA, USA
SN  - 9780769540566
N1  - This paper received the FCCB 2010 Best Paper Award
KW  - Approximate tandem repeat
KW  - dynamic programming
KW  - systolic array
KW  - FPGA
KW  - DNA;
N2  - 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. 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.
ER  -

MARTÍNEK, Tomáš a Matej LEXA. Hardware Acceleration of Approximate Tandem Repeat Detection. In \textit{18th IEEE Symposium on Field-Programmable Custom Computing Machines}. Los Alamitos, CA, USA: IEEE Computer Society, 2010, s.~79-86. ISBN~978-0-7695-4056-6.

Přehled o publikaci