基于优化解集合的个体单体型重建方法

摘要

本发明公开了一种基于优化解集合的个体单体型重建方法，包括以下步骤：预处理单核苷酸多态性(single nucleotide polymorphism，SNP)矩阵，去掉对重建工作没有帮助的冗余信息，得到只含杂合位点的SNP矩阵。通过粒子群优化策略得到一个小规模的优化解集合，即只带有杂合位点的单体型对集合。最后的扩展阶段将预处理阶段删掉的SNPs重新加上，得到最终的单体型对集合。本发明提出基于小规模优化解集合求解MEC模型的个体单体型重建方法，该方法可以获得比以往相关方法更高的单体型重建率，并且在求解大规模问题时仍具有较高的执行效率。

主权项

1.一种基于优化解集合的个体单体型重建方法，包括以下步骤：(1)预处理SNP矩阵Mm×n，去掉对重建工作没有帮助的冗余信息，即删除M中所有满足条件.f0≤t或.f1≤t的列，在矩阵M中，令nx为某一列中值为x的元素个数，且.fx＝nx/(nx+n1-x)，t设置为0.2，若被删除的列中大部分非空元素值为0，则称其为0-列，否则称为1-列，将所有满足上述条件的列删除之后，得到只含杂合位点的SNP矩阵M1m1×n1；(2)通过粒子群优化策略得到一个小规模的优化解集合，即只具有杂合位点的单体型对集合，将与Pg适应值相同的k个解均保留下来，并将k个解转换成只含杂合位点的单体型对Hi’＝(hi1’，hi2)(i＝1，...，k)，以得到一个规模为k的优化解集合H’＝{H1’，...，Hk’}；采用二进制串X(x1，x2，...，xn)(xi∈{0，1})和V(v1，v2，...，vn)(vi∈{0，1})来分别表示一个粒子的位置和速度，粒子的速度表示及粒子间的运算操作定义如下：(a)粒子的速度V定义为其两次位置X1和X2之间的距离；V＝X1-X2＝(v1，...，vn)，$v_i=\left\{\begin{array}{c}0,x_{1i}=x_{2i}\\ 1,x_{1i}\ne x_{2i}\end{array}\right.i=\mathrm{1,2},...,n(b)速度V1和V2间的加法操作定义为其相应位的逻辑加，结果为速度V；V＝V1+V2＝(v1，...，vn)，vi＝v1iORv2i，i＝1，2，...，n\}.(c)粒子速度V1与概率C的乘积，结果为速度V。V＝CV1＝(v1，...，vn)，(d)速度V和位置X1间的加法操作定义为其相应位的逻辑异或，结果为位置X。X＝X1+V＝(x1，...，xn)，xi＝x1iXORvi，i＝1，2，...，n\}.适应度函数用于评价粒子的搜索性能，指导粒子群的搜索过程；某个粒子位置X及矩阵M1中的所有片断fi(i＝1，...，m1)，X的适应度函数Fitness(X)定义为：$ \mathrm{Fitness}\left(X\right)=1-\frac{E\left(X\right)}{m1\times n1},$ E\left(X\right)=\underset{i=1}{\overset{m1}{\Sigma }}\min (S(f_i,X),D(f_i,X))其中，粒子位置X表示一对仅含杂合位点的单体型(h1’，h2’)中的一条，S(fi，X)表示fi和X对应位取值相同的位点个数，D(fi，X)表示表示fi和X对应位取值相同的位点个数；E(X)表示对应于单体型对(h1’，h2’)的最少错误更正数；(3)最后的扩展阶段将预处理阶段删掉的SNPs重新加上，对于优化解集H’中只含杂合位点的单体型对Hi’＝(hi1’，hi2’)，如果某个已被删除的同合位点为0-列或1-列，则将0或1插回到单体型对(hil’，hi2’)的相应位置，以此得到扩展后的单体型对Hi＝(hi1，hi2)，扩展结束后得到最终的单体型对集合H＝\{H1，...，Hk\}。$$$