论文部分内容阅读
DNA装配问题是指把各个读出序列(reads)拼接成一条完整的DNA链，即确定原DNA链的核苷酸“A，T，C，G”的排列顺序。实验中，由于各种原因，测序得到的读出片段序列与DNA链的实际结果会有误差，这些误差会影响到用于装配的算法的性能，因此需要对测出的读出序列进行纠错。现有的算法如：ECINDEL和SRCorr都能够对实验数据进行纠错。但是它们都是根据某个读出序列出现的次数来判断它的正确性。这类算法首先选择参数k和M，若读出序列所有长度为k的子串出现的次数均大于M次，则它为正确的读出序列，即确实为原DNA链的子串。同时，还可以利用这些长度为k的子串来对原来的读出序列片段进行纠错。然而，在这些算法中，M的选择要么是一个固定值，要么是随机的，使得这些算法在纠错问题上的表现并不稳定。
本文我们计算长度为k的子串出现M次时，它的真阳性(确实为原DNA链的一部分)的概率以及假阳性和假阴性的概率。根据计算结果，作者可以选择一个最优的M值使得最后选取的子串的错误最少，即假阳性的子串与假阴性的子串的数量之和最小。作者在模拟数据和实际数据上进行了验证，与之前的纠错算法ECINDEL，SRCorr相比，作者的算法总的错误率降低了77.6％和65.1％。