Design, analysis, development and experimental validation of algorithms for high throughput sequencing mass data using the SeqAn library for biological sequence analysis

在过去的五年中，现代测序技术带来了测序能力的超级指数增长。在撰写本提案时，使用一台测序机每天可以对大约300亿个核苷酸进行测序。该提案旨在通过从多个数据集的冗余中获益的算法方法来响应所描述的基因组序列数据的增加。更具体地说，我们的目标是：1)通过仅存储与相似参考序列的差异来开发代表一个或多个基因组序列的数据结构，同时保持在所有序列中快速导航的能力。然后，我们使用这个数据结构来开发算法，将引用的子字符串索引数据结构转换为新基因组的子字符串索引，而无需从头开始重建它，并且只将差异存储到引用索引中。2)基于1)中开发的表示，开发有效地并行处理多个基因组的算法。3)通过将SeqAn扩展为提供分析大规模基因组数据所需的核心算法组件的库，以及作为设计、分析和实现最先进生物信息学算法的实验平台，弥合算法理论与实际实现之间的差距。

During the last five years modern sequencing technologies have brought a super-exponential growth of sequencing capacities. At the time of writing this proposal it is possible to sequence about 30 billion nucleotides per day using one sequencing machine. This proposal aims to respond to the described increase of genomic sequence data with algorithmic approaches that benefit from redundancies across multiple datasets. More specifically we aim at: 1) Developing a data structure representing one or more genomic sequences by storing only the differences to a similar reference sequence while maintaining the ability to navigate quickly in all sequences. We then us this data structure for developing algorithms to transform the substring index data structure of a reference to the substring index of a new genome without rebuilding it from scratch and by only storing the differences to the reference index. 2) Developing algorithms that efficiently process multiple genomes in parallel based on the representation developed in 1). 3) Bridging the gap between algorithm theory and practical implementations by extending SeqAn as a library providing the core algorithmic components required to analyze large-scale genomic data and as an experimental platform to design, analyze, and implement state-of-the-art bioinformatics algorithms.