Skip to Main content Skip to Navigation
Conference papers

TagSNP selection using weighted CSP and russian doll search with tree decomposition

Abstract : The TagSNP problem is a specific form of compression problem arising in genetics. Given a very large set of SNP (genomic positions where polymorphism is observed in a given population), the aim is to select a smallest subset of SNPs which represents the complete set of tagSNP reliably. This is possible because strong correlations existing between neighboring SNPs. Typically, besides minimizing the tagSNP set size (mostly for economical reasons), one also seek a maximally informative subset for the given size, generating di erent secondary criteria. This problem, which is also closely related to a set covering problem, can be simply described as a weighted CSP. We report here our experiments with human tag SNP data using a recently designed WCSP algorithm combining the "Russian Doll Search" algorithm with local consistency for cost functions and an active exploitation of the problem structure, through a tree decomposition of the problem.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Saturday, June 6, 2020 - 11:15:32 AM
Last modification on : Thursday, March 17, 2022 - 1:44:02 PM


TagSNP selection using weighte...
Files produced by the author(s)


  • HAL Id : hal-02813239, version 1
  • PRODINRA : 263537



David Allouche, Thomas Schiex, Simon de Givry, Martin Sanchez. TagSNP selection using weighted CSP and russian doll search with tree decomposition. CP-09 workshop on Constraint Based Methods for Bioinformatics, Sep 2009, Lisbonne, Portugal. pp.9. ⟨hal-02813239⟩



Record views


Files downloads