创建者序列重建问题MFL模型的改进算法

Improved Algorithm for the Founder Sequence Reconstruction Problem MFL Model

创建者序列重建问题即根据后代基因信息推断其祖先基因信息,最大片断长度问题(the Maximum Fragment Lengthproblem,MFL)模型是求解该问题的有效模型.Roli提出一种求解MFL模型的构造性启发式算法,该算法通过0、1取值比例来确定创建者序列的取值,且通过引入随机信息来解决0、1等比例的情形,导致求解方案的不确定性.针对该问题,提出一种有效的改进算法I-R-Heric,该算法充分利用重组体和创建者矩阵的列向0、1取值比例的相关性等启发式信息,对随机取值问题做出有效限定.实验结果显示,I-R-Heric算法能快速有效地求解MFL问题,并能获得较改进前算法更少的断点个数和更长的片段平均长度.此外,在重组体序列规模较大的情况下,I-R-Heric仍具有较高的执行效率,有很好的实用价值.

The founder sequence reconstruction problem tries to infer the ancestral gene information from the offspring one. The Maximum Fragment Length problem （MFL） is an effective mathematical model for reconstructing founder sequences. Roli et al. presented a constructive heuristic algorithm to solve the MFL model. This algorithm computes the founder sequences according to the propor- tions of 0 entries and 1 entries, and introduces random number when the proportions of 0 and 1 entries are equal. The introduction of random information produces uncertain solutions. Aiming at this problem, in this paper, an effective improved algorithm I-R-Heric is proposed. The algorithm makes full use of the relativity between the proportion of 0 and 1 entries in the column of recombinant matrix and that of founder matrix and some other heuristic information to limit the random value effectively. Experimental results indicate that I-R-Heric can solve the MFL problem efficiently and effectively, and get much fewer breakpoints and longer fragment average length than the algorithm presented by Roli et al. In addition, when the number of recombinants and SNP sites grows large, I-R-Heric is still able to find satisfied solution to this problem very quickly. Hence it is feasible in realistic applications.