Optimizing Multiple Spaced Seeds for Homology Search View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Jinbo Xu , Daniel G. Brown , Ming Li , Bin Ma

ABSTRACT

Optimized spaced seeds improve sensitivity and specificity in local homology search [1]. Recently, several authors [2-4] have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describe a linear programming-based algorithm to optimize a set of seeds. Our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70% of what can be achieved, in most reasonable models of homologous sequences. Our method achieves performance comparable to that of a greedy algorithm, but our work gives this area a mathematical foundation. More... »

PAGES

47-58

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-540-22341-2
978-3-540-27801-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27801-6_4

DOI

http://dx.doi.org/10.1007/978-3-540-27801-6_4

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Jinbo", 
        "id": "sg:person.0603660076.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0603660076.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brown", 
        "givenName": "Daniel G.", 
        "id": "sg:person.0642727740.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Ming", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Western University", 
          "id": "https://www.grid.ac/institutes/grid.39381.30", 
          "name": [
            "Department of Computer Science, University of Western Ontario, N6A 5B8, London, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ma", 
        "givenName": "Bin", 
        "id": "sg:person.01221430663.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1093/bioinformatics/18.3.440", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006017712"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-2836(05)80360-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013618994"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/640075.640083", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018184175"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2003.04.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021213181"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2003.04.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021213181"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2003.04.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021213181"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00382-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023652568"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00382-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023652568"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(81)90087-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024589839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(88)90003-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034964732"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/285055.285059", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037698707"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44888-8_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047397326", 
          "https://doi.org/10.1007/3-540-44888-8_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39763-2_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048701396", 
          "https://doi.org/10.1007/978-3-540-39763-2_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39763-2_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048701396", 
          "https://doi.org/10.1007/978-3-540-39763-2_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0219720004000661", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063004556"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511814075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098701235"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "Optimized spaced seeds improve sensitivity and specificity in local homology search [1]. Recently, several authors [2-4] have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describe a linear programming-based algorithm to optimize a set of seeds. Our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70% of what can be achieved, in most reasonable models of homologous sequences. Our method achieves performance comparable to that of a greedy algorithm, but our work gives this area a mathematical foundation.", 
    "editor": [
      {
        "familyName": "Sahinalp", 
        "givenName": "Suleyman Cenk", 
        "type": "Person"
      }, 
      {
        "familyName": "Muthukrishnan", 
        "givenName": "S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Dogrusoz", 
        "givenName": "Ugur", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-27801-6_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22341-2", 
        "978-3-540-27801-6"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "name": "Optimizing Multiple Spaced Seeds for Homology Search", 
    "pagination": "47-58", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019005750"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-27801-6_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5a8e541f099b478956842f31793605b28c90b3971db305fc864f1060b5ddca29"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-27801-6_4", 
      "https://app.dimensions.ai/details/publication/pub.1019005750"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000362_0000000362/records_87100_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-27801-6_4"
  }
]
 

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-27801-6_4'

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-27801-6_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27801-6_4'

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-27801-6_4'


 

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

137 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27801-6_4 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N5646ee057ccd4f28a48a746e52678ab4
4 schema:citation sg:pub.10.1007/3-540-44888-8_4
5 sg:pub.10.1007/978-3-540-39763-2_4
6 https://doi.org/10.1016/0022-0000(88)90003-7
7 https://doi.org/10.1016/0022-2836(81)90087-5
8 https://doi.org/10.1016/j.jcss.2003.04.002
9 https://doi.org/10.1016/s0022-2836(05)80360-2
10 https://doi.org/10.1016/s0166-218x(03)00382-2
11 https://doi.org/10.1017/cbo9780511814075
12 https://doi.org/10.1093/bioinformatics/18.3.440
13 https://doi.org/10.1142/s0219720004000661
14 https://doi.org/10.1145/285055.285059
15 https://doi.org/10.1145/640075.640083
16 schema:datePublished 2004
17 schema:datePublishedReg 2004-01-01
18 schema:description Optimized spaced seeds improve sensitivity and specificity in local homology search [1]. Recently, several authors [2-4] have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describe a linear programming-based algorithm to optimize a set of seeds. Our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70% of what can be achieved, in most reasonable models of homologous sequences. Our method achieves performance comparable to that of a greedy algorithm, but our work gives this area a mathematical foundation.
19 schema:editor N3298b9dd389e4b6192dc1cfd28d06f8e
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf N4e32dbfd208641359bc38c9c40efd5c4
24 schema:name Optimizing Multiple Spaced Seeds for Homology Search
25 schema:pagination 47-58
26 schema:productId N216101d6c2564c53b6f115b4f64d018d
27 N26eaf15744e24c49a4684d849fc7f3df
28 Ndd92efa60d8147a4a1359b7a86883b69
29 schema:publisher N1779f95fa17b4d3bb4288df2133a3650
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019005750
31 https://doi.org/10.1007/978-3-540-27801-6_4
32 schema:sdDatePublished 2019-04-16T08:18
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nc1e1789310c744d3a269487ee39eaea0
35 schema:url https://link.springer.com/10.1007%2F978-3-540-27801-6_4
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N1779f95fa17b4d3bb4288df2133a3650 schema:location Berlin, Heidelberg
40 schema:name Springer Berlin Heidelberg
41 rdf:type schema:Organisation
42 N216101d6c2564c53b6f115b4f64d018d schema:name readcube_id
43 schema:value 5a8e541f099b478956842f31793605b28c90b3971db305fc864f1060b5ddca29
44 rdf:type schema:PropertyValue
45 N26eaf15744e24c49a4684d849fc7f3df schema:name doi
46 schema:value 10.1007/978-3-540-27801-6_4
47 rdf:type schema:PropertyValue
48 N2d7c366a797c4fd89eb6290d7dfd60ab rdf:first sg:person.01221430663.16
49 rdf:rest rdf:nil
50 N3298b9dd389e4b6192dc1cfd28d06f8e rdf:first Nd8cc394f7da24b579e03c48854d68789
51 rdf:rest N9c7d26e41ffd49f7bbe7c78ea5a9abf7
52 N4e32dbfd208641359bc38c9c40efd5c4 schema:isbn 978-3-540-22341-2
53 978-3-540-27801-6
54 schema:name Combinatorial Pattern Matching
55 rdf:type schema:Book
56 N551cb37f4fba479bacfdabdb97b3979c rdf:first sg:person.0642727740.54
57 rdf:rest N6e3ca03f2ac846dab22d2558810e287f
58 N5646ee057ccd4f28a48a746e52678ab4 rdf:first sg:person.0603660076.01
59 rdf:rest N551cb37f4fba479bacfdabdb97b3979c
60 N697dd63b40b04b0188822ddf2c048b8b schema:familyName Dogrusoz
61 schema:givenName Ugur
62 rdf:type schema:Person
63 N6e3ca03f2ac846dab22d2558810e287f rdf:first sg:person.0621576316.79
64 rdf:rest N2d7c366a797c4fd89eb6290d7dfd60ab
65 N7989ac32192d41bc82e17ac8913ca435 schema:familyName Muthukrishnan
66 schema:givenName S.
67 rdf:type schema:Person
68 N8cc03984c72b45dd9a3647b9ef91e1d8 rdf:first N697dd63b40b04b0188822ddf2c048b8b
69 rdf:rest rdf:nil
70 N9c7d26e41ffd49f7bbe7c78ea5a9abf7 rdf:first N7989ac32192d41bc82e17ac8913ca435
71 rdf:rest N8cc03984c72b45dd9a3647b9ef91e1d8
72 Nc1e1789310c744d3a269487ee39eaea0 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Nd8cc394f7da24b579e03c48854d68789 schema:familyName Sahinalp
75 schema:givenName Suleyman Cenk
76 rdf:type schema:Person
77 Ndd92efa60d8147a4a1359b7a86883b69 schema:name dimensions_id
78 schema:value pub.1019005750
79 rdf:type schema:PropertyValue
80 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
81 schema:name Mathematical Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
84 schema:name Applied Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.01221430663.16 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
87 schema:familyName Ma
88 schema:givenName Bin
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16
90 rdf:type schema:Person
91 sg:person.0603660076.01 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
92 schema:familyName Xu
93 schema:givenName Jinbo
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0603660076.01
95 rdf:type schema:Person
96 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
97 schema:familyName Li
98 schema:givenName Ming
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
100 rdf:type schema:Person
101 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
102 schema:familyName Brown
103 schema:givenName Daniel G.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
105 rdf:type schema:Person
106 sg:pub.10.1007/3-540-44888-8_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047397326
107 https://doi.org/10.1007/3-540-44888-8_4
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-540-39763-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048701396
110 https://doi.org/10.1007/978-3-540-39763-2_4
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0022-0000(88)90003-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034964732
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0022-2836(81)90087-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024589839
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/j.jcss.2003.04.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021213181
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/s0022-2836(05)80360-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013618994
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/s0166-218x(03)00382-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023652568
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1017/cbo9780511814075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098701235
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1093/bioinformatics/18.3.440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006017712
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1142/s0219720004000661 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063004556
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/285055.285059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037698707
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/640075.640083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018184175
131 rdf:type schema:CreativeWork
132 https://www.grid.ac/institutes/grid.39381.30 schema:alternateName Western University
133 schema:name Department of Computer Science, University of Western Ontario, N6A 5B8, London, Ontario, Canada
134 rdf:type schema:Organization
135 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
136 schema:name School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
137 rdf:type schema:Organization
 




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


...