生物序列的一种启发式拼接算法及实现

摘 要 经典序列拼接算法--Needleman-Wunsch算法随着基因组序列的剧增其内存需求量已严重受到了制约。为了有效的解决大尺度基因组序列的比对分析，本文在贪心算法的基础上提出一种启发式的最大权通路寻找策略，其实现过程是选择两个长度较长且交叠罚分很低的结点作种子，求得两种子的最大权路径，在计算路径的权值时就判断路径长度是否小于目标序列的大致长度，若大于则停止前进，反之则选择新的不属于已有序列的片段作为新的种子进行延伸，直至长度达到目标序列的长度。实验结果显示，原始序列的样本数并不是越多越好，该启发算法在相似的条件下具有优于贪心算法的性质，并且它在占用少量内存的情况下可以获得近似于Needleman-Wunsch算法结果的最优解。