基于新一代测序技术的K单体型组装算法研究

With the deepening of research and application of haplotypes and the development of NGS technology, haplotype assembly problem has become one of the hot reaserch areas in bioinfomatics. There have been several versions of computational model to solve this problem, which are mostly NP-hard and APX-hard. This project mainly studies effective computational models and algorithms for assemblying polyploidy organism and viral quasispecies haplotypes, and the research content includes two kinds of computational problems：K (the number of haplotypes) is known and K is unknown. Firstly, the haplotype assemlby problem is extended from diploid to polyploidy. Through deeply analyzing the characteristics of NGS technology such as short fragment, high error rate and deep sequence coverage, effective comutational models for solving viral quasispecies haplotypes assembly problem will be presented; Based on such well-developed algorithmic theory as evolutionary computation and clustering technology, we will design effective and practical algorithms through analysing the potential characteristics in sequencing fragment data; Finally, an effectual software for reconstructing K haplotypes will be developed. The project will offer systematic theories and methods for assembling the polyploidy haplotypes and the viral quasispecies ones, promote the development of related disciplines, the assembly of haplotypes, and the application of haplotypes in the fields of disease detection and drug design, etc.

随着对单体型数据研究和应用的深入及新一代基因测序技术的发展，单体型组装问题已成为生物信息学的研究热点，已有多个计算模型，这些模型绝大多数为NP-难及APX-难的。本课题主要研究多倍体生物个体及病毒准种单体型组装的有效计算模型和算法，涉及两类计算问题：K(单体型个数)值已知和K值未知组装问题。课题首先将单体型组装问题从二倍体个体扩展至多倍体个体，并深入分析新一代测序技术片段较短、测序误差较大和覆盖深度大等特征，提出病毒准种单体型组装问题的有效计算模型；通过采用进化计算、聚类技术等成熟的算法理论，分析测序片段数据中潜在的数据特征，研究设计高效实用的组装算法；最终开发出行之有效的 K 单体型组装软件。本项目的研究将为多倍体个体及病毒准种单体型组装提供系统的理论和方法，推动相关学科领域的发展，有力地促进单体型组装及其在疾病检测和药物设计等相关领域的应用。

本项目瞄准单体型组装这一前沿课题，研究二倍体、多倍体生物个体及病毒准种单体型组装的高效算法，并利用生物数据集对算法进行验证和性能分析。此外本项目还对个体单体型组装问题的重要后续研究问题（系统发育问题）进行初步探索。主要研究内容包括：研究基于最少带权边删除(MWER)数学模型的二倍体单体型组装算法；研究基于带基因型信息的最少错误更正(MEC/GI)模型的单体型组装算法（单体型个数K值确定）；研究基于着色方法的病毒准种单体型组装算法（K值未定）；研发K单体型组装软件包；研究复制-丢失演化模型下的两物种小系统发育问题。. 依托本项目发表（录用）学术论文15篇，其中SCI/EI双收录的期刊论文4篇，SCI收录的期刊论文1篇，EI收录的国际会议论文3篇；受理发明专利授权2项，获软件著作权4项；培养硕士研究生13人、中青年教师3人。所取得的研究成果主要体现在以下几个方面。. (1) 二倍体单体型组装问题研究。提出求解最少带权边删除(MWER)模型的改进环基算法IHapCompass；提出求解最少错误更正(MEC/GI)模型重建二倍体单体型的的枚举算法EHD；（2）多倍体单体型组装问题的研究。针对最少错误更正(MEC)模型，提出基于遗传算法的三倍体个体单体型重建算法GTIHR；针对MEC/GI模型，将重建二倍体的枚举方法进行扩展，提出适用于三倍体和四倍体个体单体型的组装算法；（3）病毒准种单体型组装问题的研究。提出基于着色方法的病毒准种单体型重建方法；（4）单体型组装软件包的开发。分别对组装三倍体个体、四倍体个体及病毒准种单体型的实用软件包进行研发；（5）两物种小系统发育问题的研究。提出求解2-SPP-DL问题的遗传算法G2SP和模拟退火算法SA2SP。. 本项目的主要成果可以为二倍体个体、多倍体个体及病毒准种单体型组装提供系统的理论和方法，应用于新一代测序数据下单体型组装的相关领域，促进单体型组装及其在疾病检测和药物设计等相关领域的应用。