Optimal DNA Signal Recognition Models with a Fixed Amount of Intrasignal Dependency View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Broňa Brejová , Daniel G. Brown , Tomáš Vinař

ABSTRACT

We study new probabilistic models for signals in DNA. Our models allow dependencies between multiple non-adjacent positions, in a generative model we call a higher-order tree. Computing the model of maximum likelihood is equivalent in our context to computing a minimum directed spanning hypergraph, a problem we show is NP-complete. We instead compute good models using simple greedy heuristics. In practice, the advantage of using our models over more standard models based on adjacent positions is modest. However, there is a notable improvement in the estimation of the probability that a given position is a signal, which is useful in the context of probabilistic gene finding. We also show that there is little improvement by incorporating multiple signals involved in gene structure into a composite signal model in our framework, though again this gives better estimation of the probability that a site is an acceptor site signal. More... »

PAGES

78-94

Book

TITLE

Algorithms in Bioinformatics

ISBN

978-3-540-20076-5
978-3-540-39763-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-39763-2_7

DOI

http://dx.doi.org/10.1007/978-3-540-39763-2_7

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "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, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brejov\u00e1", 
        "givenName": "Bro\u0148a", 
        "id": "sg:person.0642141060.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642141060.90"
        ], 
        "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, ON, 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, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vina\u0159", 
        "givenName": "Tom\u00e1\u0161", 
        "id": "sg:person.01041305251.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01041305251.67"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1042/bst0121005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000853811"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1042/bst0121005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000853811"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007977430", 
          "https://doi.org/10.1007/978-1-4684-2001-2_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/279069.279076", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011532778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45452-7_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026720765", 
          "https://doi.org/10.1007/3-540-45452-7_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jmbi.1997.0951", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028174721"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1007465528199", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030680500", 
          "https://doi.org/10.1023/a:1007465528199"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/26.2.544", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034760089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/hmg/11.4.451", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035706971"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(93)90045-p", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038664859"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/16.2.152", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043757410"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/18.suppl_2.s100", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047266387"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/990031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048671863", 
          "https://doi.org/10.1038/990031"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/990031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048671863", 
          "https://doi.org/10.1038/990031"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/hmg/7.5.919", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051276277"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-7306(08)60465-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053178890"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/10.9.2997", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053185442"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1968.1054142", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061646459"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7551/mitpress/1120.003.0078", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1110614950"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We study new probabilistic models for signals in DNA. Our models allow dependencies between multiple non-adjacent positions, in a generative model we call a higher-order tree. Computing the model of maximum likelihood is equivalent in our context to computing a minimum directed spanning hypergraph, a problem we show is NP-complete. We instead compute good models using simple greedy heuristics. In practice, the advantage of using our models over more standard models based on adjacent positions is modest. However, there is a notable improvement in the estimation of the probability that a given position is a signal, which is useful in the context of probabilistic gene finding. We also show that there is little improvement by incorporating multiple signals involved in gene structure into a composite signal model in our framework, though again this gives better estimation of the probability that a site is an acceptor site signal.", 
    "editor": [
      {
        "familyName": "Benson", 
        "givenName": "Gary", 
        "type": "Person"
      }, 
      {
        "familyName": "Page", 
        "givenName": "Roderic D. M.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-39763-2_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-20076-5", 
        "978-3-540-39763-2"
      ], 
      "name": "Algorithms in Bioinformatics", 
      "type": "Book"
    }, 
    "name": "Optimal DNA Signal Recognition Models with a Fixed Amount of Intrasignal Dependency", 
    "pagination": "78-94", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026577264"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-39763-2_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7e9cec65a0e4bee08ed8bfd1739378fd8ab40dbddb3f250ff610c6b216d65bc7"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-39763-2_7", 
      "https://app.dimensions.ai/details/publication/pub.1026577264"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:05", 
    "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/0000000359_0000000359/records_29219_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-39763-2_7"
  }
]
 

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-39763-2_7'

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-39763-2_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39763-2_7'

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-39763-2_7'


 

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

139 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-39763-2_7 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N27a335eac2b74a73929728a8f6eb26a8
4 schema:citation sg:pub.10.1007/3-540-45452-7_15
5 sg:pub.10.1007/978-1-4684-2001-2_9
6 sg:pub.10.1023/a:1007465528199
7 sg:pub.10.1038/990031
8 https://doi.org/10.1006/jmbi.1997.0951
9 https://doi.org/10.1016/0166-218x(93)90045-p
10 https://doi.org/10.1016/s0167-7306(08)60465-2
11 https://doi.org/10.1042/bst0121005
12 https://doi.org/10.1093/bioinformatics/16.2.152
13 https://doi.org/10.1093/bioinformatics/18.suppl_2.s100
14 https://doi.org/10.1093/hmg/11.4.451
15 https://doi.org/10.1093/hmg/7.5.919
16 https://doi.org/10.1093/nar/10.9.2997
17 https://doi.org/10.1093/nar/26.2.544
18 https://doi.org/10.1109/tit.1968.1054142
19 https://doi.org/10.1145/279069.279076
20 https://doi.org/10.7551/mitpress/1120.003.0078
21 schema:datePublished 2003
22 schema:datePublishedReg 2003-01-01
23 schema:description We study new probabilistic models for signals in DNA. Our models allow dependencies between multiple non-adjacent positions, in a generative model we call a higher-order tree. Computing the model of maximum likelihood is equivalent in our context to computing a minimum directed spanning hypergraph, a problem we show is NP-complete. We instead compute good models using simple greedy heuristics. In practice, the advantage of using our models over more standard models based on adjacent positions is modest. However, there is a notable improvement in the estimation of the probability that a given position is a signal, which is useful in the context of probabilistic gene finding. We also show that there is little improvement by incorporating multiple signals involved in gene structure into a composite signal model in our framework, though again this gives better estimation of the probability that a site is an acceptor site signal.
24 schema:editor N6b7708a1ab41443aabd79cce2956ea08
25 schema:genre chapter
26 schema:inLanguage en
27 schema:isAccessibleForFree true
28 schema:isPartOf N19602b0bc4004d1da041b737ddd1f958
29 schema:name Optimal DNA Signal Recognition Models with a Fixed Amount of Intrasignal Dependency
30 schema:pagination 78-94
31 schema:productId N1a429039ff1f42b2beee78c892ba8768
32 N738f00b29c1344289dc0f0cb416030bc
33 Ne48cc3815bf54d0aa91693ba5291ce89
34 schema:publisher Nd750dfc0a0984db590e504581d3504e8
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026577264
36 https://doi.org/10.1007/978-3-540-39763-2_7
37 schema:sdDatePublished 2019-04-16T08:05
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Nd1482df927564ce7a5f97b3760e82dd1
40 schema:url https://link.springer.com/10.1007%2F978-3-540-39763-2_7
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N0d1dc02bd3b14d038abd4defe045d0cb rdf:first sg:person.0642727740.54
45 rdf:rest Nc249d21acfbd41dd8e233020ecb9ac95
46 N14fd1e528d83400eb68aecc98a761533 schema:familyName Benson
47 schema:givenName Gary
48 rdf:type schema:Person
49 N19602b0bc4004d1da041b737ddd1f958 schema:isbn 978-3-540-20076-5
50 978-3-540-39763-2
51 schema:name Algorithms in Bioinformatics
52 rdf:type schema:Book
53 N1a429039ff1f42b2beee78c892ba8768 schema:name doi
54 schema:value 10.1007/978-3-540-39763-2_7
55 rdf:type schema:PropertyValue
56 N27a335eac2b74a73929728a8f6eb26a8 rdf:first sg:person.0642141060.90
57 rdf:rest N0d1dc02bd3b14d038abd4defe045d0cb
58 N6b7708a1ab41443aabd79cce2956ea08 rdf:first N14fd1e528d83400eb68aecc98a761533
59 rdf:rest Nd5956aac9ee44add99a9609590c553e2
60 N738f00b29c1344289dc0f0cb416030bc schema:name dimensions_id
61 schema:value pub.1026577264
62 rdf:type schema:PropertyValue
63 Nc249d21acfbd41dd8e233020ecb9ac95 rdf:first sg:person.01041305251.67
64 rdf:rest rdf:nil
65 Nd1482df927564ce7a5f97b3760e82dd1 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nd5956aac9ee44add99a9609590c553e2 rdf:first Ned1d479201494560a67bfc5a6dd2753f
68 rdf:rest rdf:nil
69 Nd750dfc0a0984db590e504581d3504e8 schema:location Berlin, Heidelberg
70 schema:name Springer Berlin Heidelberg
71 rdf:type schema:Organisation
72 Ne48cc3815bf54d0aa91693ba5291ce89 schema:name readcube_id
73 schema:value 7e9cec65a0e4bee08ed8bfd1739378fd8ab40dbddb3f250ff610c6b216d65bc7
74 rdf:type schema:PropertyValue
75 Ned1d479201494560a67bfc5a6dd2753f schema:familyName Page
76 schema:givenName Roderic D. M.
77 rdf:type schema:Person
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
82 schema:name Statistics
83 rdf:type schema:DefinedTerm
84 sg:person.01041305251.67 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
85 schema:familyName Vinař
86 schema:givenName Tomáš
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01041305251.67
88 rdf:type schema:Person
89 sg:person.0642141060.90 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
90 schema:familyName Brejová
91 schema:givenName Broňa
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642141060.90
93 rdf:type schema:Person
94 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
95 schema:familyName Brown
96 schema:givenName Daniel G.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
98 rdf:type schema:Person
99 sg:pub.10.1007/3-540-45452-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026720765
100 https://doi.org/10.1007/3-540-45452-7_15
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
103 https://doi.org/10.1007/978-1-4684-2001-2_9
104 rdf:type schema:CreativeWork
105 sg:pub.10.1023/a:1007465528199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030680500
106 https://doi.org/10.1023/a:1007465528199
107 rdf:type schema:CreativeWork
108 sg:pub.10.1038/990031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048671863
109 https://doi.org/10.1038/990031
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1006/jmbi.1997.0951 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028174721
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0166-218x(93)90045-p schema:sameAs https://app.dimensions.ai/details/publication/pub.1038664859
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/s0167-7306(08)60465-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053178890
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1042/bst0121005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000853811
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1093/bioinformatics/16.2.152 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043757410
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1093/bioinformatics/18.suppl_2.s100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047266387
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1093/hmg/11.4.451 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035706971
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1093/hmg/7.5.919 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051276277
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1093/nar/10.9.2997 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053185442
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1093/nar/26.2.544 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034760089
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1109/tit.1968.1054142 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646459
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1145/279069.279076 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011532778
134 rdf:type schema:CreativeWork
135 https://doi.org/10.7551/mitpress/1120.003.0078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110614950
136 rdf:type schema:CreativeWork
137 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
138 schema:name School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
139 rdf:type schema:Organization
 




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


...