Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1021910429.pdf (564.04 KB)

ETD Abstract Container

Abstract Header

A SCALABLE ARCHITECTURE FOR HIGH SPEED DNA PATTERN MATCHING

KATAM, SHRAVANTHI
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1021910429

Abstract Details

2002, MS, University of Cincinnati, Engineering : Computer Engineering.
The DNA sequence databases have been doubling in size every 18 months or so. This has forced the development of software and hardware systems for managing and searching these collections. An interesting problem in Genomic research is the identification of significant patterns of bases that provide control signals to the cellular protein-production machinery, a symbolic pattern recognition task for which computers are particularly well suited. The immense volume of data requires a large amount of time and computational effort to perform a simple database search. Given a string 'P' (|P|= m) called the pattern and a longer string 'T' (|T|=n) called the text, the exact matching problem is to find all occurrences, if any, of pattern 'P' in text 'T'. Many software algorithms have been developed to reduce the complexity from Θ(mn) to Θ(m+n). In this thesis, a special purpose hardware based system is described for finding clusters of patterns (max|P| = 30),in a DNA sequence, defined over a specific alphabet. By doing a number(d) of parallel computations, the complexity is further reduced to Θ(n/d). The architecture is scalable and is designed to be implemented on Virtex FPGAs. This design is extremely useful in the identification of binding sites of transcription factors.
Dr. Harold W. Carter (Advisor)
75 p.
DNA pattern matching; VLSI architecture; Hardnare Pattern Matching

Recommended Citations

Citations

  • KATAM, S. (2002). A SCALABLE ARCHITECTURE FOR HIGH SPEED DNA PATTERN MATCHING [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1021910429

    APA Style (7th edition)

  • KATAM, SHRAVANTHI. A SCALABLE ARCHITECTURE FOR HIGH SPEED DNA PATTERN MATCHING. 2002. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1021910429.

    MLA Style (8th edition)

  • KATAM, SHRAVANTHI. "A SCALABLE ARCHITECTURE FOR HIGH SPEED DNA PATTERN MATCHING." Master's thesis, University of Cincinnati, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1021910429

    Chicago Manual of Style (17th edition)

ucin1021910429
2,018
© 2002, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.