分子标记多位点排序的并行计算

为了对一组连锁的分子标记位点获得正确的排序进而构建生物遗传连锁图谱,提出了并行算法PMMASLH,针对F2作图群体,通过基于消息传递接口并行最大最小蚂蚁系统求解连锁的多个分子标记位点排序,使用隐马尔可夫模型计算一列有序标记位点所获得的极大似然值作为排序的目标函数。计算机模拟结果表明,该算法执行效率高、计算稳定,排序的功效优于著名的连锁作图软件Mapmaker。     

多序列的近似LCS改进算法

提出2种针对3条源序列的近似LCS算法,近似因子均为1/|?|。其中,线性近似LCS算法的时空复杂度均为 , 为最长源序列的长度,适于解决大规模问题。递归近似LCS算法时空复杂度均为O(nlogn),适于要求高精度问题。同时,这2种算法都能用于解决多序列的LCS和CLCS问题。实验验证了这2种算法的有效性。