A Practical Heuristic Algorithm for the Minimum Founder Set Reconstructive Problem

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. In this paper, the minimum founder set problem is studied. A practical heuristic algorithm HMFS is presented for solving the problem, which partitions the sites of founders into three parts and reconstructs them respectively. Experimental results show that HMFS can solve the minimum founder set problem fast and effectively. Furthermore, when the number of recombinants and SNP sites grows large, HMFS is still able to find satisfied solution to this problem very quickly. Hence it is practical in realistic applications.