TagSNP selection using weighted CSP and russian doll search with tree decomposition - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2009

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.
Fichier principal
Vignette du fichier
TagSNP selection using weighted CSP ans russian doll search with tree decomposition_TS_1.pdf (571.36 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02813239 , version 1 (06-06-2020)

Identifiers

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

Cite

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⟩
20 View
5 Download

Share

Gmail Mastodon Facebook X LinkedIn More