Skip to Main content Skip to Navigation
Journal articles

Minimum Mosaic Inference of a Set of Recombinants

Abstract : In this paper, we investigate the central problem of finding recombination events. It is commonly assumed that a present population is a descendent of a small number of specific sequences called founders. The recombination process consists in given two equal length sequences, generates a third sequence of the same length by concatenating the prefix of one sequence with the suffix of the other sequence. Due to recombination, a present sequence (called a recombinant) is thus composed of blocks from the founders. A major question related to founder sequences is the so-called Minimum Mosaic problem: using the natural parsimony criterion for the number of recombinations, find the best founders. In this article, we prove that the Minimum Mosaic problem given haplotype recombinants with no missing values is NP-hard when the number of founders is given as part of the input and propose some exact exponential-time algorithms for the problem, which can be considered polynomial provided some extra information. Notice that Rastas and Ukkonen proved that the Minimum Mosaic problem is NP-hard using a somewhat unrealistic mutation cost function. The aim of this paper is to provide a better complexity insight of the problem.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00679269
Contributor : Guillaume Blin <>
Submitted on : Thursday, March 15, 2012 - 1:44:52 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Monday, June 18, 2012 - 4:16:29 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Blin, Romeo Rizzi, Florian Sikora, Stéphane Vialette. Minimum Mosaic Inference of a Set of Recombinants. International Journal of Foundations of Computer Science, World Scientific Publishing, 2013, 24 (1), pp.51-66. ⟨10.1142/S0129054113400042⟩. ⟨hal-00679269⟩

Share

Metrics

Record views

674

Files downloads

1689