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 N23108cd7952a48fa959e39566e126992
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 Nbcda7b5e658949bbada1fb89abf99e67
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf N63b365f1ff174ad481cdf1cf212f80e2
24 schema:name Optimizing Multiple Spaced Seeds for Homology Search
25 schema:pagination 47-58
26 schema:productId Na8ed94172e17456ba30fad9210d5fd8a
27 Ne2172e5ca96a49fc8b11ef4466257334
28 Ne8d3c94047604d139ed63b316fd22d5b
29 schema:publisher N182dbdef474e423288ec3eb3fa48db79
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 N6514d5db5e634328b2cf6cd158ca98d5
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 N16ca9deb403c48d09d4dc36b7eabbce6 schema:familyName Muthukrishnan
40 schema:givenName S.
41 rdf:type schema:Person
42 N182dbdef474e423288ec3eb3fa48db79 schema:location Berlin, Heidelberg
43 schema:name Springer Berlin Heidelberg
44 rdf:type schema:Organisation
45 N1d03c1207e1041b0b9954e1c12a65f98 schema:familyName Dogrusoz
46 schema:givenName Ugur
47 rdf:type schema:Person
48 N1efaddc3318642d2989398345f28e79c rdf:first sg:person.0621576316.79
49 rdf:rest N873a5ead79874a7aa0fa81921dbb2082
50 N207f1252a7944f7a977240ed323c2132 rdf:first N16ca9deb403c48d09d4dc36b7eabbce6
51 rdf:rest Nf417e04350f94c239544c6101608883d
52 N23108cd7952a48fa959e39566e126992 rdf:first sg:person.0603660076.01
53 rdf:rest N80a567608f034e1fb0816e2d75f6be31
54 N3142196f77884edca76f85e753e72a62 schema:familyName Sahinalp
55 schema:givenName Suleyman Cenk
56 rdf:type schema:Person
57 N63b365f1ff174ad481cdf1cf212f80e2 schema:isbn 978-3-540-22341-2
58 978-3-540-27801-6
59 schema:name Combinatorial Pattern Matching
60 rdf:type schema:Book
61 N6514d5db5e634328b2cf6cd158ca98d5 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N80a567608f034e1fb0816e2d75f6be31 rdf:first sg:person.0642727740.54
64 rdf:rest N1efaddc3318642d2989398345f28e79c
65 N873a5ead79874a7aa0fa81921dbb2082 rdf:first sg:person.01221430663.16
66 rdf:rest rdf:nil
67 Na8ed94172e17456ba30fad9210d5fd8a schema:name readcube_id
68 schema:value 5a8e541f099b478956842f31793605b28c90b3971db305fc864f1060b5ddca29
69 rdf:type schema:PropertyValue
70 Nbcda7b5e658949bbada1fb89abf99e67 rdf:first N3142196f77884edca76f85e753e72a62
71 rdf:rest N207f1252a7944f7a977240ed323c2132
72 Ne2172e5ca96a49fc8b11ef4466257334 schema:name dimensions_id
73 schema:value pub.1019005750
74 rdf:type schema:PropertyValue
75 Ne8d3c94047604d139ed63b316fd22d5b schema:name doi
76 schema:value 10.1007/978-3-540-27801-6_4
77 rdf:type schema:PropertyValue
78 Nf417e04350f94c239544c6101608883d rdf:first N1d03c1207e1041b0b9954e1c12a65f98
79 rdf:rest rdf:nil
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)


...