单体型装配问题及其算法(英文)

单核苷酸多态性(SNP)单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误,重构出尽可能与原来片段一致的单体型.这个问题有几个不同的模型最少片段去除(MFR)问题,最少SNP去除(MSR)问题以及最少错误纠正(MEC)问题.前两个问题的复杂性与算法已有一些学者研究过.第三个问题已被证明是NP完全问题,但这个问题的实际算法还没有.该文对MEC问题给出了一个分支定界算法,这个算法能得到问题的全局最优解.通过这个算法对实际数据的计算说明了MEC模型的合理性,即在一定条件下,通过修正最少的错误重构出的单体型确实是真实的单体型.由于分支定界算法对这样一个NP完全问题不能在可接受的时间内解规模较大的问题,文中又给出了求解MEC问题的两个基于动态聚类的算法,以便对规模较大的问题在可接受的时间内得到近似最优解.数值实际表明这两个算法很快,很有效.这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这两个算法是有效的、实际的算法.

单体型装配问题的研究现状

单核苷酸多态性(SNP)是指不同个体DNA序列上的单个碱基的差异,是人类基因组中最丰富的遗传变异。单体型是指位于一条染色体上或某一区域的一组相关联的SNP等位基因。研究表明在复杂性疾病研究方面,由多个变异位点组合构成的单体型所携带的信息比单个的SNP数据的信息更有价值,由此衍生了单体型装配问题。文章论述了SNP,单体型,基因型的定义,综述了求解单一个体单体型装配问题的主要模型及算法,同时阐述了求解群体单体型装配问题的5种方法及算法。

单体型装配问题的启发式算法研究

单体型装配问题是生物信息学的一个研究重点,针对的是染色体上的大量SNP数据,通过适当的方法,将其装配成一对单体型。文章介绍了求解单体型装配问题的三种主要的启发式算法,分别是基于遗传算法的启发式算法,基于粒子群算法的启发式算法和基于前馈神经网络算法的启发式算法。

基于加权粒子群算法的单体型装配问题

针对单体型装配问题的特点,提出一种求解该问题的加权粒子群算法。通过对DALY数据库ID13进行测试,表明算法有效性。同时,与基础粒子群算法和遗传算法进行比较,表明我们所设计的算法在单体型重构率上优于两者。