Algorithmic challenges in population scale genomics

该提案旨在通过高通量测序技术解决数据爆炸带来的一些算法挑战。我们的目标是通过新颖的算法方法，弥合数据生成能力与管理、存储、通信和分析能力之间的差距，数据生成能力的增长速度超过了摩尔定律。通常，我们的算法方法依赖于组合优化，数据结构，近似算法和组合模式匹配技术。我们的目标是开发新的方法，旨在通过重新排序来自高通量测序平台的读段，同时压缩和索引基因组序列数据，现有的压缩和映射技术将应用于该平台。这种增强技术的动机是局部一致性解析技术，这是第一次应用于基因组学在这个建议。 在这个提议中要解决的算法挑战的核心是同时发现多个相关基因组之间的结构变异问题。我们将开发新的组合配方和启发式技术的近似算法文献的激励下，其解决方案。 我们还将专注于通过将它们与其他形式的高通量生物数据（如基因表达和网络表示的相互作用信息）相关联来识别生物学上重要的结构变体。

This proposal aims to address some of the algorithmic challenges offered by data explosion through high throughput sequencing technologies. We aim to bridge the gap between the capacity to generate data, which is growing faster than the Moore's Law, and the ability to manage, store, communicate and analyze it, through novel algorithmic approaches. Typically our algorithmic approaches rely on combinatorial optimization, data structures, approximation algorithms and techniques from combinatorial pattern matching. We will aim to develop novel methods aiming to simultaneously compress and index genome sequence data through re-ordering reads coming from high throughput sequencing platforms on which existing compression and mapping technologies will be applied. This boosting technique for is motivated by the Locally Consistent Parsing technique, which is applied the first time to genomics in this proposal. At the heart of the algorithmic challenges to be addressed in this proposal is the simultaneous discovery of structural variation among multiple related genomes problem. We will develop novel combinatorial formulations and heuristic techniques motivated by approximation algorithms literature for its solution. We will also focus on identifying biologically important structural variants through correlating them with other forms of high throughput biological data such as gene expression and interaction information represented as a network.