论文部分内容阅读
分析和识别单体型对复杂疾病致病基因的精确定位有重要作用。单体型组装问题是利用个体DNA测序片段数据推出该个体一对单体型的计算问题。根据不同的优化准则,单体型组装问题有最少SNP(Single Nucleotide Polymorphisms)位点删除模型(Minimum SNP Removal, MSR),最少片段删除模型(Minimum Fragment Removal,MFR)和最少错误更正模型(Minimum Error Correction, MEC)等计算模型,这些模型旨在得到问题的一个最优解,即两条单体型。对生物学家来说,一个解对于复杂的生物问题往往是不够的。基于上述目的,本文为MSR、MFR和MEC设计了能给出多个最优解的模型和相应的参数化枚举算法。MSR模型是试图删除最少SNP位点来确定个体的单体型的计算问题。在此基础上,我们定义MSR的k枚举模型(k-Minimum SNP Removal Enumeration, K_MSR):对于给定的一个SNP矩阵M,一个小正整数k,为MSR模型枚举最多k个解,即得到一个元素个数为k的最优解的集合。我们设计求解K MSR的算法的时间复杂度为O(nk1k2+nkk1+mlogm+mk1),空间复杂度为O(nkk1),其中m为片段数,n为SNP位点数,k1为单个片段覆盖的最大SNP位点数,k2为覆盖任意SNP位点的最大片段数。MFR模型是试图删除最少片段来确定个体单体型的计算问题,在MFR模型的定义的基础上我们提出K_MFR (k-Minimum FragmentRemoval Enumeration)模型：给定一个SNP矩阵M和一个小正整数k,为MFR模型枚举最多k个最优解。我们设计求解该模型算法的时间复杂度为O(mkk22+mkk1k2+mlogm+nk2),空间复杂度为O(mk1+mkk22)。在MEC模型定义的基础上,我们提出MEC的k枚举模型(k-Minimum Error Correction Enumeration,K_MEC),并设计了时间复杂度为O(nk22k2+mlogm+mk1)、空间复杂度为O(mkk12k2+nk2)的算法。大量实验表明上述几种算法可有效提供多个解,可提供较高重建率的单体型,得到的多个解能为为生物学家提供更多选择,对于复杂问题的研究有很大实际意义。