New decoding algorithms for Hidden Markov Models using distance measures on labellings View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-01

AUTHORS

Daniel G Brown, Jakub Truszkowski

ABSTRACT

BACKGROUND: Existing hidden Markov model decoding algorithms do not focus on approximately identifying the sequence feature boundaries. RESULTS: We give a set of algorithms to compute the conditional probability of all labellings "near" a reference labelling lambda for a sequence y for a variety of definitions of "near". In addition, we give optimization algorithms to find the best labelling for a sequence in the robust sense of having all of its feature boundaries nearly correct. Natural problems in this domain are NP-hard to optimize. For membrane proteins, our algorithms find the approximate topology of such proteins with comparable success to existing programs, while being substantially more accurate in estimating the positions of transmembrane helix boundaries. CONCLUSION: More robust HMM decoding may allow for better analysis of sequence features, in reasonable runtimes. More... »

PAGES

s40

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1186/1471-2105-11-s1-s40

DOI

http://dx.doi.org/10.1186/1471-2105-11-s1-s40

DIMENSIONS

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

PUBMED

https://www.ncbi.nlm.nih.gov/pubmed/20122214


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Algorithms", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Databases, Protein", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Markov Chains", 
        "type": "DefinedTerm"
      }, 
      {
        "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
        "name": "Membrane Proteins", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "David R. Cheriton 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": [
            "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Truszkowski", 
        "givenName": "Jakub", 
        "id": "sg:person.01320220640.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01320220640.40"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-30219-3_36", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000399524", 
          "https://doi.org/10.1007/978-3-540-30219-3_36"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30219-3_36", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000399524", 
          "https://doi.org/10.1007/978-3-540-30219-3_36"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/bti1014", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008444097"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkl200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014110611"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jmb.2004.03.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021467321"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jmbi.1998.2107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027169738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-11-s1-s28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031992141", 
          "https://doi.org/10.1186/1471-2105-11-s1-s28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btg1057", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034588758"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-6-s4-s12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039318188", 
          "https://doi.org/10.1186/1471-2105-6-s4-s12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1083156239", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1083334419", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511790492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098676015"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-01", 
    "datePublishedReg": "2010-01-01", 
    "description": "BACKGROUND: Existing hidden Markov model decoding algorithms do not focus on approximately identifying the sequence feature boundaries.\nRESULTS: We give a set of algorithms to compute the conditional probability of all labellings \"near\" a reference labelling lambda for a sequence y for a variety of definitions of \"near\". In addition, we give optimization algorithms to find the best labelling for a sequence in the robust sense of having all of its feature boundaries nearly correct. Natural problems in this domain are NP-hard to optimize. For membrane proteins, our algorithms find the approximate topology of such proteins with comparable success to existing programs, while being substantially more accurate in estimating the positions of transmembrane helix boundaries.\nCONCLUSION: More robust HMM decoding may allow for better analysis of sequence features, in reasonable runtimes.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1186/1471-2105-11-s1-s40", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1023786", 
        "issn": [
          "1471-2105"
        ], 
        "name": "BMC Bioinformatics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "Suppl 1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "11"
      }
    ], 
    "name": "New decoding algorithms for Hidden Markov Models using distance measures on labellings", 
    "pagination": "s40", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f7b8d714f77844dc51bf5aa7030a0165fc5986fd9947e2f2ddff7dc71eee8749"
        ]
      }, 
      {
        "name": "pubmed_id", 
        "type": "PropertyValue", 
        "value": [
          "20122214"
        ]
      }, 
      {
        "name": "nlm_unique_id", 
        "type": "PropertyValue", 
        "value": [
          "100965194"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1186/1471-2105-11-s1-s40"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052005567"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1186/1471-2105-11-s1-s40", 
      "https://app.dimensions.ai/details/publication/pub.1052005567"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T16:49", 
    "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/0000000001_0000000264/records_8669_00000551.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1186/1471-2105-11-S1-S40"
  }
]
 

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.1186/1471-2105-11-s1-s40'

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.1186/1471-2105-11-s1-s40'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-11-s1-s40'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-11-s1-s40'


 

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

125 TRIPLES      21 PREDICATES      44 URIs      25 LITERALS      13 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1186/1471-2105-11-s1-s40 schema:about N016fec242c40422a9bdc4a6a703050b0
2 N3462b801e79c4a5d83249592ff5c03f3
3 N3deddc7360a44b3ca7d5d7a044f34144
4 Nf1980fd924ce4c0db9c4df946000b6cd
5 anzsrc-for:08
6 anzsrc-for:0802
7 schema:author Nd09ce77856e048cfa81e560dc3a5de6f
8 schema:citation sg:pub.10.1007/978-3-540-30219-3_36
9 sg:pub.10.1186/1471-2105-11-s1-s28
10 sg:pub.10.1186/1471-2105-6-s4-s12
11 https://app.dimensions.ai/details/publication/pub.1083156239
12 https://app.dimensions.ai/details/publication/pub.1083334419
13 https://doi.org/10.1006/jmbi.1998.2107
14 https://doi.org/10.1016/j.jmb.2004.03.016
15 https://doi.org/10.1017/cbo9780511790492
16 https://doi.org/10.1093/bioinformatics/btg1057
17 https://doi.org/10.1093/bioinformatics/bti1014
18 https://doi.org/10.1093/nar/gkl200
19 schema:datePublished 2010-01
20 schema:datePublishedReg 2010-01-01
21 schema:description BACKGROUND: Existing hidden Markov model decoding algorithms do not focus on approximately identifying the sequence feature boundaries. RESULTS: We give a set of algorithms to compute the conditional probability of all labellings "near" a reference labelling lambda for a sequence y for a variety of definitions of "near". In addition, we give optimization algorithms to find the best labelling for a sequence in the robust sense of having all of its feature boundaries nearly correct. Natural problems in this domain are NP-hard to optimize. For membrane proteins, our algorithms find the approximate topology of such proteins with comparable success to existing programs, while being substantially more accurate in estimating the positions of transmembrane helix boundaries. CONCLUSION: More robust HMM decoding may allow for better analysis of sequence features, in reasonable runtimes.
22 schema:genre research_article
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N05bbe14c98204a9cbd4693da1375b38e
26 Nd2a0a46edfe448039d5b719cf8cad7ba
27 sg:journal.1023786
28 schema:name New decoding algorithms for Hidden Markov Models using distance measures on labellings
29 schema:pagination s40
30 schema:productId N2b9d3a63c4cf4b43a0fb3d118cf8bcc5
31 N345d266798ac4c9a9fd5f1868a1b6ab1
32 N4390f458ecf343a0bfd6b8a55c433341
33 Nd21a14969dd445bca1afe7ae9a5c6180
34 Ne23c0bbe8cfd46fcba1b5fc83d4fec0e
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052005567
36 https://doi.org/10.1186/1471-2105-11-s1-s40
37 schema:sdDatePublished 2019-04-10T16:49
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Na70e258d06f84f12ac5caa3d5305868d
40 schema:url http://link.springer.com/10.1186/1471-2105-11-S1-S40
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N016fec242c40422a9bdc4a6a703050b0 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
45 schema:name Algorithms
46 rdf:type schema:DefinedTerm
47 N05bbe14c98204a9cbd4693da1375b38e schema:volumeNumber 11
48 rdf:type schema:PublicationVolume
49 N2b9d3a63c4cf4b43a0fb3d118cf8bcc5 schema:name doi
50 schema:value 10.1186/1471-2105-11-s1-s40
51 rdf:type schema:PropertyValue
52 N345d266798ac4c9a9fd5f1868a1b6ab1 schema:name pubmed_id
53 schema:value 20122214
54 rdf:type schema:PropertyValue
55 N3462b801e79c4a5d83249592ff5c03f3 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
56 schema:name Membrane Proteins
57 rdf:type schema:DefinedTerm
58 N3deddc7360a44b3ca7d5d7a044f34144 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
59 schema:name Databases, Protein
60 rdf:type schema:DefinedTerm
61 N4390f458ecf343a0bfd6b8a55c433341 schema:name readcube_id
62 schema:value f7b8d714f77844dc51bf5aa7030a0165fc5986fd9947e2f2ddff7dc71eee8749
63 rdf:type schema:PropertyValue
64 N464eb6f04cbc480ea6b5a66db83d5dc8 rdf:first sg:person.01320220640.40
65 rdf:rest rdf:nil
66 Na70e258d06f84f12ac5caa3d5305868d schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Nd09ce77856e048cfa81e560dc3a5de6f rdf:first sg:person.0642727740.54
69 rdf:rest N464eb6f04cbc480ea6b5a66db83d5dc8
70 Nd21a14969dd445bca1afe7ae9a5c6180 schema:name dimensions_id
71 schema:value pub.1052005567
72 rdf:type schema:PropertyValue
73 Nd2a0a46edfe448039d5b719cf8cad7ba schema:issueNumber Suppl 1
74 rdf:type schema:PublicationIssue
75 Ne23c0bbe8cfd46fcba1b5fc83d4fec0e schema:name nlm_unique_id
76 schema:value 100965194
77 rdf:type schema:PropertyValue
78 Nf1980fd924ce4c0db9c4df946000b6cd schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
79 schema:name Markov Chains
80 rdf:type schema:DefinedTerm
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 sg:journal.1023786 schema:issn 1471-2105
88 schema:name BMC Bioinformatics
89 rdf:type schema:Periodical
90 sg:person.01320220640.40 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
91 schema:familyName Truszkowski
92 schema:givenName Jakub
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01320220640.40
94 rdf:type schema:Person
95 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
96 schema:familyName Brown
97 schema:givenName Daniel G
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
99 rdf:type schema:Person
100 sg:pub.10.1007/978-3-540-30219-3_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000399524
101 https://doi.org/10.1007/978-3-540-30219-3_36
102 rdf:type schema:CreativeWork
103 sg:pub.10.1186/1471-2105-11-s1-s28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031992141
104 https://doi.org/10.1186/1471-2105-11-s1-s28
105 rdf:type schema:CreativeWork
106 sg:pub.10.1186/1471-2105-6-s4-s12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039318188
107 https://doi.org/10.1186/1471-2105-6-s4-s12
108 rdf:type schema:CreativeWork
109 https://app.dimensions.ai/details/publication/pub.1083156239 schema:CreativeWork
110 https://app.dimensions.ai/details/publication/pub.1083334419 schema:CreativeWork
111 https://doi.org/10.1006/jmbi.1998.2107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027169738
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/j.jmb.2004.03.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021467321
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1017/cbo9780511790492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098676015
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1093/bioinformatics/btg1057 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034588758
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1093/bioinformatics/bti1014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008444097
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1093/nar/gkl200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014110611
122 rdf:type schema:CreativeWork
123 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
124 schema:name David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
125 rdf:type schema:Organization
 




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


...