A Randomized Iterated Greedy Algorithm for the Founder Sequence Reconstruction Problem

The problem of inferring ancestral genetic information in terms of a set of founders of a given population arises in various biological contexts. In optimization terms, this problem can be formulated as a combinatorial string problem. The main problem of existing techniques, both exact and heuristic, is that their time complexity scales exponentially, which makes them impractical for solving large-scale instances. Basing our work on previous ideas outlined in previous work of two of the authors of this paper, we developed a new constructive greedy iterative algorithm able to provide solutions in a short time span and that statistically dominates the hybrid tabu search proposed in that paper.