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.