Tight Approximability Results for Test Set Problems in Bioinformatics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Piotr Berman , Bhaskar DasGupta , Ming-Yang Kao

ABSTRACT

In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished” by a family of “tests”, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of “basic” tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem. More... »

PAGES

39-50

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27810-8_5

DOI

http://dx.doi.org/10.1007/978-3-540-27810-8_5

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.16753.36", 
          "name": [
            "Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "id": "sg:person.011536202643.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be \u201cdistinguished\u201d by a family of \u201ctests\u201d, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of \u201cbasic\u201d tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem.", 
    "editor": [
      {
        "familyName": "Hagerup", 
        "givenName": "Torben", 
        "type": "Person"
      }, 
      {
        "familyName": "Katajainen", 
        "givenName": "Jyrki", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-27810-8_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22339-9", 
        "978-3-540-27810-8"
      ], 
      "name": "Algorithm Theory - SWAT 2004", 
      "type": "Book"
    }, 
    "keywords": [
      "graph coloring problem", 
      "multi-valued functions", 
      "upper bounds", 
      "coloring problem", 
      "universe of objects", 
      "approximation ratio", 
      "set problem", 
      "simple version", 
      "universe", 
      "sufficient collection", 
      "important version", 
      "variety of applications", 
      "problem", 
      "small alphabets", 
      "different notions", 
      "approximability", 
      "bounds", 
      "most versions", 
      "version", 
      "objects", 
      "strings", 
      "applications", 
      "basic tests", 
      "terms", 
      "alphabet", 
      "function", 
      "notion", 
      "bioinformatics", 
      "variation", 
      "subset", 
      "substrings", 
      "analysis", 
      "variety", 
      "ratio", 
      "collection", 
      "test", 
      "family", 
      "presence", 
      "Union", 
      "DNA sequence analysis", 
      "sequence analysis", 
      "paper"
    ], 
    "name": "Tight Approximability Results for Test Set Problems in Bioinformatics", 
    "pagination": "39-50", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011847704"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-27810-8_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-27810-8_5", 
      "https://app.dimensions.ai/details/publication/pub.1011847704"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_12.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-27810-8_5"
  }
]
 

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-27810-8_5'

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-27810-8_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27810-8_5'

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-27810-8_5'


 

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

127 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27810-8_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N16fb9b65a9844d428447a17822a2a251
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished” by a family of “tests”, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of “basic” tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem.
7 schema:editor N18bb8eb91bd34d40b475eafaaa47d226
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc0b93376e193460cb9a736e5f4a0c227
12 schema:keywords DNA sequence analysis
13 Union
14 alphabet
15 analysis
16 applications
17 approximability
18 approximation ratio
19 basic tests
20 bioinformatics
21 bounds
22 collection
23 coloring problem
24 different notions
25 family
26 function
27 graph coloring problem
28 important version
29 most versions
30 multi-valued functions
31 notion
32 objects
33 paper
34 presence
35 problem
36 ratio
37 sequence analysis
38 set problem
39 simple version
40 small alphabets
41 strings
42 subset
43 substrings
44 sufficient collection
45 terms
46 test
47 universe
48 universe of objects
49 upper bounds
50 variation
51 variety
52 variety of applications
53 version
54 schema:name Tight Approximability Results for Test Set Problems in Bioinformatics
55 schema:pagination 39-50
56 schema:productId N593e151c411d4d228ff471028a8155e5
57 N677e82668a13418c85ded69b49fced42
58 schema:publisher Ncfd24dd4e4754feda42c0cd4787f9466
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011847704
60 https://doi.org/10.1007/978-3-540-27810-8_5
61 schema:sdDatePublished 2022-05-20T07:41
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N21d3a212155c4b4399038058893b355b
64 schema:url https://doi.org/10.1007/978-3-540-27810-8_5
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N16fb9b65a9844d428447a17822a2a251 rdf:first sg:person.01274506210.27
69 rdf:rest Ne4c9d066ec05470a92b8aedf862ff70e
70 N18bb8eb91bd34d40b475eafaaa47d226 rdf:first N3c615deaee114a5c9434937543e713d9
71 rdf:rest N58687986097b48f593d56afe3b9f3709
72 N21d3a212155c4b4399038058893b355b schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N2da6571677074c018d5f5fbbd8665764 rdf:first sg:person.011536202643.55
75 rdf:rest rdf:nil
76 N3c615deaee114a5c9434937543e713d9 schema:familyName Hagerup
77 schema:givenName Torben
78 rdf:type schema:Person
79 N58687986097b48f593d56afe3b9f3709 rdf:first Nf693cdbfa0214ada82f908053095c43f
80 rdf:rest rdf:nil
81 N593e151c411d4d228ff471028a8155e5 schema:name doi
82 schema:value 10.1007/978-3-540-27810-8_5
83 rdf:type schema:PropertyValue
84 N677e82668a13418c85ded69b49fced42 schema:name dimensions_id
85 schema:value pub.1011847704
86 rdf:type schema:PropertyValue
87 Nc0b93376e193460cb9a736e5f4a0c227 schema:isbn 978-3-540-22339-9
88 978-3-540-27810-8
89 schema:name Algorithm Theory - SWAT 2004
90 rdf:type schema:Book
91 Ncfd24dd4e4754feda42c0cd4787f9466 schema:name Springer Nature
92 rdf:type schema:Organisation
93 Ne4c9d066ec05470a92b8aedf862ff70e rdf:first sg:person.0763403270.10
94 rdf:rest N2da6571677074c018d5f5fbbd8665764
95 Nf693cdbfa0214ada82f908053095c43f schema:familyName Katajainen
96 schema:givenName Jyrki
97 rdf:type schema:Person
98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
99 schema:name Information and Computing Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
102 schema:name Computation Theory and Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.011536202643.55 schema:affiliation grid-institutes:grid.16753.36
105 schema:familyName Kao
106 schema:givenName Ming-Yang
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55
108 rdf:type schema:Person
109 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
110 schema:familyName Berman
111 schema:givenName Piotr
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
113 rdf:type schema:Person
114 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
115 schema:familyName DasGupta
116 schema:givenName Bhaskar
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
118 rdf:type schema:Person
119 grid-institutes:grid.16753.36 schema:alternateName Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA
120 schema:name Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA
121 rdf:type schema:Organization
122 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
123 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
124 rdf:type schema:Organization
125 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
126 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
127 rdf:type schema:Organization
 




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


...