DNA序列拼接中de Bruijn图结构的研究

基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能一次性获得,需要利用序列拼接技术对实验中获得的DNA片段进行拼接操作.目前,测序过程中获得的DNA片段越来越短,基于Euler路径的拼接算法在处理这种短片段拼按时具有优势.在Euler路径算法中,一个关键的步骤是de Bruijn图的构建,一直...     

基于函数变换的求解SAT问题的新算法

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题。随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的。实验结果表明:与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高。     

DNA序列拼接中de Bruijn图结构的研究

基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能一次性获得,需要利用序列拼接技术对实验中获得的DNA片段进行拼接操作。目前,测序过程中获得的DNA片段越来越短,基于Euler路径的拼接算法在处理这种短片段拼接时具有优势。在Euler路径算法中,一个关键的步骤是deBruijn图的构建,一直以来,构建deBruijn图的方式总是让后一个κ-mer与前一个κ-mer之间有κ-1个碱基的交叠,相邻的两个κ-mer之间相互错开一位。但文中的研究发现,如果有边连接的两个κ-mer之间有κ-2个或者更少的碱基相交叠,会对deBruijn图结构复杂性产生重要影响。针对这些影响进行详细分析,并设计实验进行验证,实验结果表明,κ-mer之间的错位数变化对deBruijn图结构复杂性有显著影响。