Skip to Main content Skip to Navigation
Conference papers

Minimum Mosaic Inference of a Set of Recombinants

Abstract : In this paper, we investigate the central problem of finding recombination events (Kececioglu & Gusfield 1998, Ukkonen 2002, Schwartz et al. 2002, Koivisto et al. 2004, Rastas & Ukkonen 2007, Wu & Gusfield 2007). It is commonly assumed that a present population is a descendent of a small number of specific sequences called founders. 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 hard for an unbounded number of founders and propose some exact exponential-time algorithms for the problem. Notice that, in (Rastas & Ukkonen 2007), Rastas et al. proved that the Minimum Mosaic problem is hard using a somewhat unrealistic mutation cost function (details provided afterwards). The aim of this paper is to provide a better complexity insight of the problem.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Saturday, October 22, 2011 - 4:51:44 PM
Last modification on : Saturday, January 15, 2022 - 3:56:04 AM
Long-term archiving on: : Monday, January 23, 2012 - 2:20:30 AM


Files produced by the author(s)


  • HAL Id : hal-00620371, version 1


Guillaume Blin, Romeo Rizzi, Florian Sikora, Stéphane Vialette. Minimum Mosaic Inference of a Set of Recombinants. 17th Computing: the Australasian Theory Symposium (CATS'11), Jan 2011, Perth, Australia. pp.23-30. ⟨hal-00620371⟩



Record views


Files downloads