Bioinformatics algorithms: from sequence to structure and function

本提案旨在部分解决我们将在未来几年在分子生物学、生物化学和遗传学方面面临的一些基本计算挑战。特别是，我们建议开发新的算法和数据结构，使下一代测序技术在结构变异检测，拷贝数变异检测和SNP检测方面具有成本效益和有用，从而开发新一代基于基因组学的诊断技术。我们还建议研究一些涉及字符串和序列的基础算法问题。此外，我们将致力于开发生物分子网络分析，RNA结构和相互作用预测以及小分子分析的新算法，超越我们一直在研究的QSAR方法。我们的方法将基于对问题的严格数学建模，然后通过具有性能和正确性保证的算法来解决问题。我们将使用的技术通常基于近似算法、随机算法、组合优化、数据结构和计算学习理论。

This proposal aims to address in part a number of fundamental computational challenges we will be facing in molecular biology, biochemistry and genetics in the coming few years. In particular we propose to develop novel algorithms and data structures for making next generation sequencing technologies cost effective and useful for structural variation detection, copy number variation detection and SNP detection towards developing a new generation of genomics based diagnostic technologies. We also propose to work on some foundational algorithmic problems involving strings and sequences. In addition, we will aim to develop novel algorithms for biomolecular network analysis, RNA structure and interaction prediction and small molecule analysis, going beyond the QSAR methods we have been working on. Our approach will be based on rigorous mathematical modeling of the problems which will then be tackled through algorithms with performance and correctness guarantees. The techniques we will use are typically based on approximation algorithms, randomized algorithms, combinatorial optimization, data structures and computational learning theory.