Design and Analysis of Algorithms for Small Error Target String Selection, Strip Extraction and Binding Substructure Identification

In this project, the researchers will design algorithms for the following three important problems in computational biology: the small error target string selection problem, the maximal strip recovery problem, and the problem of finding protein complementary binding substructures.The target string selection problem is one of the core problems in motif detection. It has many applications in biology, such as finding targets for potential drugs, creating diagnostic probes for bacterial infection, creating universal PCR primers, and creating unbiased consensus sequences. In many applications, the error is required to be very small. Here the researchers will design efficient fixed-parameter algorithms when the error is small. The maximal strip recovery problem is formulated in the first step of comparative genomics. The problem is to decompose two genomes into synteny blocks, i.e., segments of chromosomes deemed to be homologous in the two genomes. Efficient methods for solving this problem will play important roles in comparative genomics. The problem of finding protein complementary binding substructures is formulated in protein-protein interaction (PPI) binding sites identification. It is crucial in determining how proteins interact in the post-genomic era.The project will emphasize algorithmic issues for all the proposed problems. For the first and third problems, they intend to design algorithms and produce efficient software packages.