论文部分内容阅读
创建者序列重建问题即根据后代基因信息推断其祖先基因信息,最大片断长度问题(the Maximum Fragment Lengthproblem,MFL)模型是求解该问题的有效模型.Roli提出一种求解MFL模型的构造性启发式算法,该算法通过0、1取值比例来确定创建者序列的取值,且通过引入随机信息来解决0、1等比例的情形,导致求解方案的不确定性.针对该问题,提出一种有效的改进算法I-R-Heric,该算法充分利用重组体和创建者矩阵的列向0、1取值比例的相关性等启发式信息,对随机取值问题做出有效限定.实验结果显示,I-R-Heric算法能快速有效地求解MFL问题,并能获得较改进前算法更少的断点个数和更长的片段平均长度.此外,在重组体序列规模较大的情况下,I-R-Heric仍具有较高的执行效率,有很好的实用价值.
The creator sequence reconstruction problem is to infer the ancestral gene information and the maximum fragment length problem (MFL) model according to the offspring gene information, which is an effective model to solve the problem.Roli proposed a constructive heuristic algorithm to solve the MFL model , The algorithm determines the value of the creator’s sequence by using the ratio of 0 and 1, and resolves the case of 0,1 equal proportion by introducing random information, which leads to the uncertainty of the solution. Aiming at this problem, The algorithm, IR-Heric, makes full use of the heuristic information such as the correlation between the columns of the recombinants and the creator matrix to the ratio of 0 to 1. The experimental results show that IR- Heric algorithm can solve the MFL problem quickly and effectively, and can get fewer number of breakpoints and longer fragment mean length than the former algorithm.In addition, IR-Heric still has the advantage High execution efficiency, have very good practical value.