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.