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

https://hal.inrae.fr/hal-02813239
Contributor : Migration Prodinra <>
Submitted on : Saturday, June 6, 2020 - 11:15:32 AM
Last modification on : Wednesday, April 21, 2021 - 11:08:03 AM

File

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

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

28

Files downloads

17