多倍体单体型从头组装算法研究

Some economically important plants have more than two copies of each chromosome. Constructing the DNA sequence of each copy of chromosome by DNA sequencing, i.e. haplotype assembly, is valuable to crop improvement. Current algorithms of haplotype assembly for polyploids have to align the DNA reads to reference genomes and cannot be applied to the polyploids without known reference genomes. .The project focuses on algorithms of haplotype assembly for polyploids without known reference genomes based on DNA reads from multiple sequencing platforms. The project will use a De Bruijn graph to construct high reliable contigs from short reads with a low error rate, and use contig-based alignment, cluster analysis and machine learning to correct the sequencing errors of reads. Then local assemblies of the contigs and the related reads will be conducted via overlap-extension approaches. Based on the information provided by long reads, paired-end reads, local assemblies and contigs, we will propose haplotype assembly optimal models to deal with the challenge caused by the large and rich repeats of polyploid plant genomes and the fact that difference ratios varies much between different haplotype pairs. Furthermore, we will combine parameterized computation, dynamic programming, advanced graph algorithm and other algorithm designing techniques, design fast and effective algorithms to solve the optimal models, and construct the DNA sequence for each haplotype. Efficient and accurate algorithms of de novo haplotype assembly will prompt genome sequencing of polyploids.

一些重要经济作物的体细胞有多套染色体组，利用测序技术确定每套染色体的DNA序列，即单体型组装，对作物改良有重要意义。当前多倍体单体型组装算法需要把测序读段联配到参考基因组上，无法应用于参考基因组未知的多倍体。.本课题研究无需参考基因组序列、融合多平台测序数据的多倍体单体型从头组装算法。本课题将基于De Bruijn图在错误率低的短读段数据上构建可信度高的contig集，通过基于contig的联配，用聚类分析、机器学习等手段进行读段纠错；用重叠-扩展方式对contig及相关读段进行局部组装，在长读段、paired-end读段、局部组装和contig数据基础上针对多倍体植物基因组重复率高、各单体型对之间差异率明显不同的特征建立优化模型；结合参数计算、动态规划和高级图算法等技术设计快速有效求解算法，构建各单体型的DNA序列。高效精确的多倍体单体型从头组装算法将促进多倍体生物全基因组测序工程。

一些重要经济作物的体细胞有多套染色体组，利用测序技术确定每套染色体的DNA序列， 即单体型组装，对作物改良有重要意义。本课题主要研究无需参考基因组序列、融合多平台测序数据的多倍体单体型从头组装算法。本课题对各主流测序平台上异源多倍体基因组序列真实数据进行了各方面的统计分析，通过对序列数据特征的提取，设计出了能根据测序平台相关参数生成与真实数据有相同特征的模拟数据的生成器。提出基于拓扑结构和相关读段覆盖为依据的 contig 的可信度评价指标，设计基于De Bruijn图的contig组装算法。通过对各主流测序平台上异源多倍体基因组序列真实数据进行统计分析完成了序列数据特征的提取，对异源多倍体基因组序列的组装框架进行了初步的设计，提出了基于第二代测序技术的短序列对错误率较高的长序列进行纠错，利用纠错后的长序列进行组装的算法。利用近年来提出的一种有效的高精度scaffolding方法光学作图（Optimal mapping），本项目提出了一个新颖的光学作图scaffolding方法OMGS(Optical Map-based Genome Scaffolding) ，一次能接收多个optimal map，设计了高效的算法求解scaffolding中的连续性和正确性的优化问题。项目组还对微生物-疾病互作、lncRNA-蛋白质异构体互作、蛋白质异构体功能预测、等相关问题进行了研究，利用已知的疾病-微生物关联网络，通过集成疾病相似性和微生物相似性，提出了二部图推荐算法预测新的疾病-微生物关联；根据基因序列和表达数据提出了lncRNA-蛋白质异构体交互预测、蛋白质异构体功能预测的深度学习方法。