• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Minimum Mosaic Inference of a Set of Recombinants

Blin, Guillaume; Vialette, Stéphane; Sikora, Florian; Rizzi, Romeo (2013), Minimum Mosaic Inference of a Set of Recombinants, International Journal of Foundations of Computer Science, 24, 1, p. 51-66. 10.1142/S0129054113400042

Type
Article accepté pour publication ou publié
External document link
https://hal-upec-upem.archives-ouvertes.fr/hal-00679269
Date
2013
Journal name
International Journal of Foundations of Computer Science
Volume
24
Number
1
Publisher
World Scientific
Pages
51-66
Publication identifier
10.1142/S0129054113400042
Metadata
Show full item record
Author(s)
Blin, Guillaume

Vialette, Stéphane

Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Rizzi, Romeo
Abstract (EN)
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.
Subjects / Keywords
SNP; Minimum mosaic problem; complexity; haplotype

Related items

Showing items related by title and author.

  • Thumbnail
    Some Results on More Flexible Versions of Graph Motif 
    Rizzi, Romeo; Sikora, Florian (2015) Article accepté pour publication ou publié
  • Thumbnail
    Extension of Vertex Cover and Independent Set in Some Classes of Graphs 
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Thumbnail
    Neural Maximum Independent Set 
    Pontoizeau, Thomas; Sikora, Florian; Yger, Florian; Cazenave, Tristan (2022) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo