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

职业：通过组合和几何技术解决生物信息学计算问题的有效算法

• 批准号: 0346973
• 负责人: Bhaskar DasGupta
• 金额: $ 40万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-04-15 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0346973&HistoricalAwards=false
• 关键词: CAREER; Efficient; Algorithms; Computational; Problems

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.

该项目应用组合和几何优化技术为生物信息学的三个重要研究领域设计有效的算法：（1）子结构相似性识别； (2)蛋白质逆折叠； (3)测试集问题。有效的算法是通过使用组合方法来设计的，例如信息内容启发式方法、局部比率和多阶段技术、切片和切块方法以及通过原始对偶模式的线性规划方法。 现有和新颖的组合技术的明智组合，加上与其他计算生物学家的合作，以及与生物学家和生物工程师的有效互动和反馈，使得设计的算法具有实用性和生物学相关性。这项工作的技术影响将在于设计有效的算法来应对计算挑战通过组合/几何技术解决上述领域的问题。这将为生物学家提供更好的算法和软件，用于多种应用，例如通过发现不同蛋白质的相似子结构来识别蛋白质片段水平上的远程进化关系，以及通过字符串条形码有效检测未知病原体。该提案的更广泛影响将是整合研究和教学，通过出版物、网络和其他方式进行有效传播，以及提高研究和教育的多样性。