An Evolutionary Approach to the Non-unique Oligonucleotide Probe Selection Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Lili Wang , Alioune Ngom , Robin Gras , Luis Rueda

ABSTRACT

In order to accurately measure the gene expression levels in microarray experiments, it is crucial to design unique, highly specific and sensitive oligonucleotide probes for the identification of biological agents such as genes in a sample. Unique probes are difficult to obtain for closely related genes such as the known strains of HIV genes. The non-unique probe selection problem is to select a probe set that is able to uniquely identify targets in a biological sample, while containing a minimal number of probes. This is an NP-hard problem. We define a probe selection function that allows to decide which are the best probes to include in or exclude from a candidate probe set. We then propose a new deterministic greedy heuristic that uses the selection for solving the non-unique probe selection problem. Finally, we combine the selection function with an evolutionary method for finding near minimal non-unique probe sets. When used on benchmark data sets, our greedy method outperforms current greedy heuristics for non-unique probe selection in most instances. Our genetic algorithm also produced excellent results when compared to advanced methods introduced in the literature for the non-unique probe selection problem. More... »

PAGES

143-162

Book

TITLE

Transactions on Computational Systems Biology X

ISBN

978-3-540-92272-8
978-3-540-92273-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-92273-5_8

DOI

http://dx.doi.org/10.1007/978-3-540-92273-5_8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1030393489


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0604", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Genetics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.267455.7", 
          "name": [
            "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lili", 
        "id": "sg:person.010316333663.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010316333663.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.267455.7", 
          "name": [
            "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ngom", 
        "givenName": "Alioune", 
        "id": "sg:person.01356713372.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356713372.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.267455.7", 
          "name": [
            "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gras", 
        "givenName": "Robin", 
        "id": "sg:person.0712313416.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712313416.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.267455.7", 
          "name": [
            "School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rueda", 
        "givenName": "Luis", 
        "id": "sg:person.013110677001.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013110677001.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "In order to accurately measure the gene expression levels in microarray experiments, it is crucial to design unique, highly specific and sensitive oligonucleotide probes for the identification of biological agents such as genes in a sample. Unique probes are difficult to obtain for closely related genes such as the known strains of HIV genes. The non-unique probe selection problem is to select a probe set that is able to uniquely identify targets in a biological sample, while containing a minimal number of probes. This is an NP-hard problem. We define a probe selection function that allows to decide which are the best probes to include in or exclude from a candidate probe set. We then propose a new deterministic greedy heuristic that uses the selection for solving the non-unique probe selection problem. Finally, we combine the selection function with an evolutionary method for finding near minimal non-unique probe sets. When used on benchmark data sets, our greedy method outperforms current greedy heuristics for non-unique probe selection in most instances. Our genetic algorithm also produced excellent results when compared to advanced methods introduced in the literature for the non-unique probe selection problem.", 
    "editor": [
      {
        "familyName": "Priami", 
        "givenName": "Corrado", 
        "type": "Person"
      }, 
      {
        "familyName": "Dressler", 
        "givenName": "Falko", 
        "type": "Person"
      }, 
      {
        "familyName": "Akan", 
        "givenName": "Ozgur B.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ngom", 
        "givenName": "Alioune", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-92273-5_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-92272-8", 
        "978-3-540-92273-5"
      ], 
      "name": "Transactions on Computational Systems Biology X", 
      "type": "Book"
    }, 
    "keywords": [
      "non-unique probe selection problem", 
      "probe selection problem", 
      "minimal non-unique probe sets", 
      "probe sets", 
      "gene expression levels", 
      "sensitive oligonucleotide probes", 
      "Non-unique Oligonucleotide Probe Selection Problem", 
      "related genes", 
      "microarray experiments", 
      "genes", 
      "oligonucleotide probes", 
      "expression levels", 
      "selection function", 
      "non-unique probe selection", 
      "probe selection", 
      "probe", 
      "candidate probes", 
      "evolutionary approach", 
      "selection", 
      "biological samples", 
      "HIV genes", 
      "biological agents", 
      "unique probe", 
      "function", 
      "strains", 
      "identification", 
      "target", 
      "evolutionary method", 
      "data sets", 
      "most instances", 
      "levels", 
      "set", 
      "minimal number", 
      "number", 
      "agents", 
      "good probe", 
      "experiments", 
      "samples", 
      "advanced methods", 
      "results", 
      "approach", 
      "instances", 
      "method", 
      "order", 
      "literature", 
      "problem", 
      "benchmark data sets", 
      "genetic algorithm", 
      "greedy method", 
      "NP-hard problem", 
      "algorithm", 
      "greedy heuristic", 
      "selection problem", 
      "heuristics", 
      "excellent results", 
      "probe selection function", 
      "new deterministic greedy heuristic", 
      "deterministic greedy heuristic", 
      "non-unique probe sets", 
      "current greedy heuristics", 
      "Oligonucleotide Probe Selection Problem"
    ], 
    "name": "An Evolutionary Approach to the Non-unique Oligonucleotide Probe Selection Problem", 
    "pagination": "143-162", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030393489"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-92273-5_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-92273-5_8", 
      "https://app.dimensions.ai/details/publication/pub.1030393489"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_360.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-92273-5_8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92273-5_8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92273-5_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92273-5_8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92273-5_8'


 

This table displays all metadata directly associated to this object as RDF triples.

157 TRIPLES      23 PREDICATES      87 URIs      80 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-92273-5_8 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author N350dda0a41c34eeb9a8f5a8401a1f842
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description In order to accurately measure the gene expression levels in microarray experiments, it is crucial to design unique, highly specific and sensitive oligonucleotide probes for the identification of biological agents such as genes in a sample. Unique probes are difficult to obtain for closely related genes such as the known strains of HIV genes. The non-unique probe selection problem is to select a probe set that is able to uniquely identify targets in a biological sample, while containing a minimal number of probes. This is an NP-hard problem. We define a probe selection function that allows to decide which are the best probes to include in or exclude from a candidate probe set. We then propose a new deterministic greedy heuristic that uses the selection for solving the non-unique probe selection problem. Finally, we combine the selection function with an evolutionary method for finding near minimal non-unique probe sets. When used on benchmark data sets, our greedy method outperforms current greedy heuristics for non-unique probe selection in most instances. Our genetic algorithm also produced excellent results when compared to advanced methods introduced in the literature for the non-unique probe selection problem.
7 schema:editor N1be215c4dbde41c2960b2f62e66dc99d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb139b3bc3fb44186ab909244b57c770e
12 schema:keywords HIV genes
13 NP-hard problem
14 Non-unique Oligonucleotide Probe Selection Problem
15 Oligonucleotide Probe Selection Problem
16 advanced methods
17 agents
18 algorithm
19 approach
20 benchmark data sets
21 biological agents
22 biological samples
23 candidate probes
24 current greedy heuristics
25 data sets
26 deterministic greedy heuristic
27 evolutionary approach
28 evolutionary method
29 excellent results
30 experiments
31 expression levels
32 function
33 gene expression levels
34 genes
35 genetic algorithm
36 good probe
37 greedy heuristic
38 greedy method
39 heuristics
40 identification
41 instances
42 levels
43 literature
44 method
45 microarray experiments
46 minimal non-unique probe sets
47 minimal number
48 most instances
49 new deterministic greedy heuristic
50 non-unique probe selection
51 non-unique probe selection problem
52 non-unique probe sets
53 number
54 oligonucleotide probes
55 order
56 probe
57 probe selection
58 probe selection function
59 probe selection problem
60 probe sets
61 problem
62 related genes
63 results
64 samples
65 selection
66 selection function
67 selection problem
68 sensitive oligonucleotide probes
69 set
70 strains
71 target
72 unique probe
73 schema:name An Evolutionary Approach to the Non-unique Oligonucleotide Probe Selection Problem
74 schema:pagination 143-162
75 schema:productId N5eadea34a7174c7fa8b9601212362c49
76 Na9437601038048dd8f02a4c4914f3746
77 schema:publisher Nb0348ab9044543f6881d050c8d1251c6
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030393489
79 https://doi.org/10.1007/978-3-540-92273-5_8
80 schema:sdDatePublished 2021-11-01T18:57
81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
82 schema:sdPublisher N596c35da2119413d9c249c8aeec0194f
83 schema:url https://doi.org/10.1007/978-3-540-92273-5_8
84 sgo:license sg:explorer/license/
85 sgo:sdDataset chapters
86 rdf:type schema:Chapter
87 N1be215c4dbde41c2960b2f62e66dc99d rdf:first N63bfa180232340dbb2ff24bf24e75879
88 rdf:rest N51f97af07ad94f9996d5786fc000ea8a
89 N1e852b800ff943eabcb3b34db4b87cd5 schema:familyName Akan
90 schema:givenName Ozgur B.
91 rdf:type schema:Person
92 N2f438973113e447b86d905a2622cb5cb schema:familyName Dressler
93 schema:givenName Falko
94 rdf:type schema:Person
95 N350dda0a41c34eeb9a8f5a8401a1f842 rdf:first sg:person.010316333663.39
96 rdf:rest N64a3932ee02749fbb35ad717207e85e9
97 N51f97af07ad94f9996d5786fc000ea8a rdf:first N2f438973113e447b86d905a2622cb5cb
98 rdf:rest N7e54b9585b2c4a40b8c8645a37aa1f5b
99 N596c35da2119413d9c249c8aeec0194f schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 N5eadea34a7174c7fa8b9601212362c49 schema:name dimensions_id
102 schema:value pub.1030393489
103 rdf:type schema:PropertyValue
104 N63bfa180232340dbb2ff24bf24e75879 schema:familyName Priami
105 schema:givenName Corrado
106 rdf:type schema:Person
107 N64a3932ee02749fbb35ad717207e85e9 rdf:first sg:person.01356713372.35
108 rdf:rest Ncf2087ced41b4b3e9a016f61d11359ee
109 N7e54b9585b2c4a40b8c8645a37aa1f5b rdf:first N1e852b800ff943eabcb3b34db4b87cd5
110 rdf:rest N9351b371b9bf4338a0fca83c52c50485
111 N9351b371b9bf4338a0fca83c52c50485 rdf:first Nec29134f47c5465ebf5bcd57caa29e9b
112 rdf:rest rdf:nil
113 Na9437601038048dd8f02a4c4914f3746 schema:name doi
114 schema:value 10.1007/978-3-540-92273-5_8
115 rdf:type schema:PropertyValue
116 Nb0348ab9044543f6881d050c8d1251c6 schema:name Springer Nature
117 rdf:type schema:Organisation
118 Nb139b3bc3fb44186ab909244b57c770e schema:isbn 978-3-540-92272-8
119 978-3-540-92273-5
120 schema:name Transactions on Computational Systems Biology X
121 rdf:type schema:Book
122 Nc4bff8fe5191459b85e14358ef99854c rdf:first sg:person.013110677001.28
123 rdf:rest rdf:nil
124 Ncf2087ced41b4b3e9a016f61d11359ee rdf:first sg:person.0712313416.43
125 rdf:rest Nc4bff8fe5191459b85e14358ef99854c
126 Nec29134f47c5465ebf5bcd57caa29e9b schema:familyName Ngom
127 schema:givenName Alioune
128 rdf:type schema:Person
129 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
130 schema:name Biological Sciences
131 rdf:type schema:DefinedTerm
132 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
133 schema:name Genetics
134 rdf:type schema:DefinedTerm
135 sg:person.010316333663.39 schema:affiliation grid-institutes:grid.267455.7
136 schema:familyName Wang
137 schema:givenName Lili
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010316333663.39
139 rdf:type schema:Person
140 sg:person.013110677001.28 schema:affiliation grid-institutes:grid.267455.7
141 schema:familyName Rueda
142 schema:givenName Luis
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013110677001.28
144 rdf:type schema:Person
145 sg:person.01356713372.35 schema:affiliation grid-institutes:grid.267455.7
146 schema:familyName Ngom
147 schema:givenName Alioune
148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356713372.35
149 rdf:type schema:Person
150 sg:person.0712313416.43 schema:affiliation grid-institutes:grid.267455.7
151 schema:familyName Gras
152 schema:givenName Robin
153 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712313416.43
154 rdf:type schema:Person
155 grid-institutes:grid.267455.7 schema:alternateName School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada
156 schema:name School of Computer Science, 5115 Lambton Tower, University of Windsor, 401 Sunset Avenue, N9B 3P4, Windsor, Ontario, Canada
157 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...