Formal development of a reconfigurable tool for parallel DNA matching

Author

Abdallah, A.E. ; Simiakakis, G. ; Theoharis, T.

Author_Institution

Centre for Appl. Formal Methods, South Bank Univ., London, UK

Volume

1

fYear

2000

fDate

2000

Firstpage

268

Abstract

DNA matching is a computationally demanding task. The Human Genome Project is producing huge quantities of data, which have to be analyzed. A formal description of the task of searching a DNA sequence is given and an efficient parallel algorithm is derived using formal methods. The algorithm is implemented on an FPGA using Handel-C, a language that enables the compilation of high-level algorithms directly into gate level synchronous hardware, thus reducing the development time. The designed algorithm makes no assumptions about DNA transformations, and is therefore a very powerful tool. It can be used in conjunction with an expert system to automatically detect patterns of interest in the DNA

Keywords

DNA; field programmable gate arrays; formal verification; medical expert systems; reconfigurable architectures; string matching; DNA transformations; FPGA; Handel-C; Human Genome Project; development time; expert system; formal methods; gate level synchronous hardware; high-level algorithms; parallel DNA matching; reconfigurable tool; Algorithm design and analysis; Bioinformatics; DNA computing; Expert systems; Field programmable gate arrays; Genomics; Hardware; Humans; Parallel algorithms; Sequences;

fLanguage

English

Publisher

ieee

Conference_Titel

Electronics, Circuits and Systems, 2000. ICECS 2000. The 7th IEEE International Conference on

Conference_Location

Jounieh

Print_ISBN

0-7803-6542-9

Type

conf

DOI

10.1109/ICECS.2000.911534

Filename

911534