PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

最大节约原则下单倍型推导问题的实用算法

在疾病的易感基因研究和药物反应实验中,常常需要知道单倍型,而不仅仅是基因型数据.但是直接通过生物学实验手段来测定单倍型在时间和成本上消耗过大,所以在实验室里往往仅测得基因型,而通过一些计算手段来推导出单倍型.不同于Clark著名的单倍型推导模型,Gusfield和Wang等人提出了一种通过基因型样本推导单倍型的新模型.这种模型试图按照最大节约原则去寻找可以解释基因型样本的最小单倍型集合.这种基于节约原则的模型克服了Clark模型的一些缺陷.提出了节约原则模型的一个多项式时间的贪心算法以及一种把贪心策略和分支限界策略集合在统一框架下的复合算法.相对于Wang原来提出的分支限界完全算法,贪心的近似算法运行快得多,而且同时保持了比较准确的推导结果.新的复合算法也是一种完全算法.实验结果表明,与原来的分支限界算法相比,复合算法可以极大地提高运行效率以及可应用的实例规模.     

三元家庭基因数据的单体分型和单体型频率估计

研究了在门德尔遗传定理和哈代-维恩伯格平衡假设下,三元家庭基因型数据的单体分型和单体型频率估计问题.过去的研究仅仅关注个体间没有联系或者含有一般家系信息的基因型数据,而对这种特殊的三元家庭关注得不够.考虑到HAPMAP数据库中有一部分数据就基于这种三元家庭,现在有越来越多的需求要求直接分析这种特殊的家系结构.提出一个两段式的三元家庭中单体型频率的估计方法:i) 分型阶段,找出每一个三元家庭零重组单体构型;ii) 频率估计阶段,在前一阶段得到的单体构型基础上,应用EM算法来估计单体型频率.在程序包TRIOHAP中用C语言实现了单体分型算法和EM算法,并且使用模拟和实际数据测试了TRIOHAP的有效性和效率.实验结果表明,TRIOHAP要比其他那些忽略了三元家庭信息的常见单体型频率估计软件运行快很多.进一步地,由于TRIOHAP利用了这些信息,其估计结果更加可靠.