ABSTRACT

This project applies combinatorial and geometric optimization techniques to design efficient algorithms for three important research areas in bioinformatics: (1) substructure similarity identification; (2) inverse protein folding; and (3) test set problems. Efficient algorithms are designed by using combinatorial methods such as the information content heuristic approach, local-ratio and multi-phase techniques, slice-and-dice methods, and a linear programming approach via primal-dual schema. Judicious combinations of existing and novel combinatorial techniques coupled with collaborations with other computational biologists and effective interactions with and feedback from the biologists and bioengineers makes the designed algorithms practical and biologically relevant.

The technical impact of this work will be in designing efficient algorithms for computationally challenging problems in the abovementioned areas via combinatorial/geometric techniques. This will provide the biologists with better algorithms and software for several applications such as recognizing remote evolutionary relationships at the level of protein fragments via discovering similar substructures from different proteins and efficiently detecting unknown pathogens via string barcoding. The broader impacts of this proposal will be integrating research and teaching, effective dissemination via publications, web and other means, and improving diversity in research and education.

Please report errors in award information by writing to: awardsearch@nsf.gov.