Volume 8 Number 11 (Nov. 2013)
Home > Archive > 2013 > Volume 8 Number 11 (Nov. 2013) >
JCP 2013 Vol.8(11): 2942-2950 ISSN: 1796-203X
doi: 10.4304/jcp.8.11.2942-2950

Constructing the Minimum Founder Set from a Set of Recombinant Sequences

Jingli Wu and Zhaocan Wang
College of Computer Science and Information Technology, Guangxi Normal University, Guilin, 541004, China

Abstract—Genetic recombination plays an important role in shaping the within-species genetic variations. It has been generally accepted that current-day population evolved from a small number of specific sequences called founders, and the genomic sequences (called recombinants) of individuals within the population are composed of segments from the founders due to recombination. A related computational problem is the so-called Minimum Founder Set problem: construct the minimum founder set from a set of given recombinant sequences so that the minimum fragment length is not less than the given fragment length bound. Ukkonen presented a segmentation based dynamic programming (SDYN) algorithm to solve it. However, the number of reconstructed founders obtained by the SDYN algorithm is restricted by the given fragment length bound in a certain situation. In this paper, a practical constructive heuristic algorithm HMFS is proposed for solving the problem. The HMFS algorithm partitions the sites of founders into three parts and reconstructs them respectively. Experimental results show that the HMFS algorithm can reconstruct a founder set very quickly, and the solutions obtained by the HMFS algorithm are close to or better than those obtained by the SDYN algorithm. In addition, the HMFS algorithm runs much faster than the SDYN algorithm, it is still efficient for solving large size problems.

Index Terms—bioinformatics, minimum founder set problem, recombinant, founder, reconstruction, heuristic, algorithm

[PDF]

Cite: Jingli Wu and Zhaocan Wang, " Constructing the Minimum Founder Set from a Set of Recombinant Sequences," Journal of Computers vol. 8, no. 11, pp. 2942-2950, 2013.

General Information

ISSN: 1796-203X
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 13, 2018 News!

    Vol 13, No 10 has been published with online version   [Click]

  • Apr 28, 2019 News!

    Vol 14, No 4 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

    Vol 14, No 3 has been published with online version   [Click]

  • Feb 22, 2019 News!

    Vol 14, No 2 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Jan 04, 2019 News!

    Vol 14, No 1 has been published with online version   [Click]

  • Read more>>