University of Houston
Department of Computer Science

In partial fulfillment of the Requirements for the Degree of
Master of Science


Andrey Belokrylov
will defend his thesis

New Algorithms and Data Structures for the Identification of the Minimum Combination of Probes/Primers for Pathogen Detection

Abstract

Developing rapid, reliable and inexpensive nucleic acid-based assays for the identification of pathogens is a very critical yet challenging problem. Since the cost of an assay is directly proportional to the number of oligonucleotides (probes and/or primers) it contains, the computational challenge is to identify the combination consisting of the minimum number of probes/primers which satisfy the assays’ constraints, is able to detect (cover) only the pathogens of interest (target organisms), and is blind to other organisms that may be present in the sample. Unfortunately, the problem of identifying the minimum probe/primer set belongs to the class of NP-complete problems and thus does not have any known fast polynomial algorithmic solution. In the work presented here, three computational algorithms and twelve supporting data structures have been developed for discovering the minimum probe/primer coverage set. Comparative analysis of the three algorithms, in terms of both speed of execution and memory usage, was performed using randomly generated data sets. Using these newly developed algorithms and data structures, the minimum probe and primer sets were computed for the detection of all strains of influenza virus, human immunodeficiency virus (HIV) and dengue virus.

Date: Friday, April 20, 2007
Time: 01:30 PM
Place: 550-PGH



Faculty, students, and the general public are invited.
Thesis Advisor: Dr. Yuriy Fofanov