CAJ | 학술논문

创建者序列重建问题即根据后代基因信息推断其祖先基因信息,最大片断长度问题(the Maximum Fragment Length problem,MFL)模型是求解该问题的有效模型.Roli提出一种求解MFL模型的构造性启发式算法,该算法通过0、1取值比例来确定创建者序列的取值,且通过引入随机信息来解决0、1等比例的情形,导致求解方案的不确定性.针对该问题,提出一种有效的改进算法I-R-Heric,该算法充分利用重组体和创建者矩阵的列向0、1取值比例的相关性等启发式信息,对随机取值问题做出有效限定.实验结果显示,I-R-Heric算法能快速有效地求解MFL问题,并能获得较改进前算法更少的断点个数和更长的片段平均长度.此外,在重组体序列规模较大的情况下,I-R-Heric仍具有较高的执行效率,有很好的实用价值.
창건자서렬중건문제즉근거후대기인신식추단기조선기인신식,최대편단장도문제(the Maximum Fragment Length problem,MFL)모형시구해해문제적유효모형.Roli제출일충구해MFL모형적구조성계발식산법,해산법통과0、1취치비례래학정창건자서렬적취치,차통과인입수궤신식래해결0、1등비례적정형,도치구해방안적불학정성.침대해문제,제출일충유효적개진산법I-R-Heric,해산법충분이용중조체화창건자구진적렬향0、1취치비례적상관성등계발식신식,대수궤취치문제주출유효한정.실험결과현시,I-R-Heric산법능쾌속유효지구해MFL문제,병능획득교개진전산법경소적단점개수화경장적편단평균장도.차외,재중조체서렬규모교대적정황하,I-R-Heric잉구유교고적집행효솔,유흔호적실용개치.