【摘 要】
:
单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。但是在当前的实验技术下直接测定个体的单体型所需的时间和金钱上的花费过于昂贵,因
论文部分内容阅读
单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。但是在当前的实验技术下直接测定个体的单体型所需的时间和金钱上的花费过于昂贵,因此利用计算机技术来确定个体的单体型有极其重要的现实意义。单体型检测可分为两大类:单体型组装问题和单体型推断问题。本文主要对单体型组装问题相关模型和算法进行研究。由于单体型组装问题计算模型绝大部分是NP-hard,当片断数和SNP位点数较大时,基本上没有可行的精确算法,而诸如启发式算法、遗传算法等近似算法的近似程度很难保证,往往不能获得最优解。因而尽可能提高精确算法的时间和空间效率具有极其重要的现实意义。本文着重探索了如何利用小参数技术显著降低相关计算模型的时间和空间复杂度,并针对单体型组装加权最小字符翻转(WMLF)问题提出了一个时间复杂度为D(nk22k2+mlogm+mk1)的参数化算法,可以在较短的时间得到WMLF问题的精确解,具有良好的可扩展性和较高的实用价值。参数化算法是精确算法而且具有时空复杂度较低的特性,因此我们在现有实验条件下可利用参数化算法来比较不同计算模型的单体型重构精度。基于适用于不同模型的参数化算法,本文对MSR、MFR、MEC、WMLF、MEC/GI等单体型组装模型做了详细的分析比较,从而提出了一系列新的评价指标,然后采用真实和模拟的生物数据对相关模型进行大量实验,分析影响单体型重构精度的原因,从而为设计新的计算模型指明了思路。
其他文献
计算机和网络的广泛应用,大大地方便了人们获取信息和交流信息,同时其版权保护也变得越来越重要。而数字水印技术作为一种有效的版权保护手段越来越受到人们的青睐。近年来,
现在,电子商务正被广泛应用。人们只要有一台能上网的电脑,就可以足不出户,从网上浏览各种产品的外观,了解产品的特性,并通过网络来购买自己需要的产品。但是,当前的电子商务网站上
随着商业环境变化越来越快,竞争越来越剧烈,信息系统的交付周期越来越短,信息系统应对变化的要求越来越高。现实需要新的开发方法来加速信息系统的开发、交付周期,提高系统应
随着计算机网络技术与多媒体技术的迅速发展,多媒体数字产品越来越需要一种有效的版权保护方法。作为信息隐藏技术在计算机领域的一项重要应用,数字水印为保护多媒体信息的版
数据分类是数据挖掘的一个重要方法。数据分类是通过分析训练集数据,产生关于类别的精确描述或模式,这种类描述可以用来对未来的数据进行分类,有着广泛的应用前景。目前常用
面向服务的体系结构作为近年来软件工程领域出现的一个新兴的研究方向,其技术得到迅速发展和应用。Web服务组合技术作为实现面向服务体系结构的一项重要技术,已成为当今学术界
企事业单位通常在网络的出入口处安装多种网络安全设备以保障内部网络的安全,防火墙和IDS等设备在运行过程中会产生大量的日志来记录网络事件。通过研究这些多源异构的日志数
随着计算机网络技术的飞速发展,网络攻击和入侵事件与日俱增,网络安全风险系数不断提高,曾经作为网络安全重要保障的防火墙,已经不能满足人们对网络安全的需求。作为对防火墙
组播(Multicast)是一种同时发送数据到多个接收者的有效通信方式,应用层组播(ALM)是在端系统实现组播转发的,端系统之间通过单播连接,在应用层建立一个虚拟的Overlay网络,部分接
微电子技术、计算技术和无线通信等技术的进步,推动了低功耗多功能传感器的快速发展,使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。在研究应用于无线传