Show simple item record

dc.contributor.authorBlin, Guillaume*
dc.contributor.authorVialette, Stéphane*
dc.contributor.authorSikora, Florian*
dc.contributor.authorRizzi, Romeo*
dc.date.accessioned2013-06-21T10:58:21Z
dc.date.available2013-06-21T10:58:21Z
dc.date.issued2013
dc.identifier.issn0129-0541
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11456
dc.language.isoenen
dc.subjectSNP
dc.subjectMinimum mosaic problem
dc.subjectcomplexity
dc.subjecthaplotype
dc.subject.ddc004en
dc.titleMinimum Mosaic Inference of a Set of Recombinants
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.
dc.relation.isversionofjnlnameInternational Journal of Foundations of Computer Science
dc.relation.isversionofjnlvol24
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages51-66
dc.relation.isversionofdoi10.1142/S0129054113400042
dc.identifier.urlsitehttps://hal-upec-upem.archives-ouvertes.fr/hal-00679269
dc.relation.isversionofjnlpublisherWorld Scientific
dc.subject.ddclabelInformatique généraleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-07-13T17:14:00Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds989*
hal.person.labIds*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record