CAREER: Efficient Algorithms for Computational Problems in Bioinformatics Via Combinatorial and Geometric Techniques

该项目应用组合和几何优化技术为生物信息学中的三个重要研究领域设计了有效的算法：(1)亚结构相似性识别；(2)蛋白质反向折叠；(3)测试集问题。利用信息量启发式方法、局部比率和多阶段技术、切片和骰子方法以及基于原始-对偶模式的线性规划方法等组合方法设计了高效的算法。现有的和新的组合技术的合理组合，加上与其他计算生物学家的合作，以及与生物学家和生物工程师的有效交互和反馈，使所设计的算法具有实用性和生物学相关性。这项工作的技术影响将是通过组合/几何技术为上述领域的计算挑战问题设计高效的算法。这将为生物学家提供更好的算法和软件，用于多种应用，如通过从不同蛋白质中发现相似的亚结构来识别蛋白质片段水平上的远程进化关系，以及通过字符串条形码有效地检测未知病原体。这一建议的更广泛影响将是将研究和教学结合起来，通过出版物、网络和其他手段有效传播，并改善研究和教育的多样性。

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.