文章基本信息

标题：A Parthenogenetic Algorithm for the Founder Sequence Reconstruction Problem
本地全文：下载
作者：Wu, Jingli ; Wang, Hua
期刊名称：Journal of Computers
印刷版ISSN：1796-203X
出版年度：2013
卷号：8
期号：11
页码：2934-2941
DOI：10.4304/jcp.8.11.2934-2941
语种：English
出版社：Academy Publisher
摘要：The maximum fragment length (MFL) is an important computational model for solving the founder sequence reconstruction problem. Benedettini et al. presented a meta-heuristic algorithm BACKFORTH based on iterative greedy method. The BACKFORTH algorithm starts with a single initial solution, and iteratively alternates between a partial destruction and reconstruction in order to obtain a final solution. The kind of optimization mechanism, which is based on a single initial solution, may make the performance of the BACKFORTH algorithm sensitive to the quality of the initialization. In this paper, a practical parthenogenetic algorithm PGMFL, which is a population-based meta-heuristic method, is proposed. The PGMFL algorithm can search multiple regions of a solution space simultaneously. A novel genetic operator is introduced based on the presented heuristic algorithm HF, which takes advantage of look-ahead mechanism and some potential information, i.e., the proportions of 0 and 1 entries in a column of recombinant matrix and those in the corresponding column of the founder matrix, and some other heuristic information, to compute the column values. The PGMFL algorithm can get fewer breakpoints and longer fragment average length than the BACKFORTH algorithm, which are proved by a number of experiments.
关键词：founder;reconstruction;parthenogenetic algorithm