The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

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

ABSTRACT

Hidden Markov models (HMMs) are often used for biological sequence annotation. Each sequence element is represented by states with the same label. A sequence should be annotated with the labeling of highest probability. Computing this most probable labeling was shown NP-hard by Lyngsø and Pedersen [9]. We improve this result by proving the problem NP-hard for a fixed HMM. High probability labelings are often found by heuristics, such as taking the labeling corresponding to the most probable state path. We introduce an efficient algorithm that computes the most probable labeling for a wide class of HMMs, including models previously used for transmembrane protein topology prediction and coding region detection. More... »

PAGES

426-437

References to SciGraph publications

  • 2000. Computational Complexity of Problems on Probabilistic Grammars and Transducers in GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS
  • Book

    TITLE

    Algorithms in Bioinformatics

    ISBN

    978-3-540-23018-2
    978-3-540-30219-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_36

    DOI

    http://dx.doi.org/10.1007/978-3-540-30219-3_36

    DIMENSIONS

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


    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"
          }
        ], 
        "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": "sg:pub.10.1007/978-3-540-45257-7_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005228610", 
              "https://doi.org/10.1007/978-3-540-45257-7_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45257-7_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005228610", 
              "https://doi.org/10.1007/978-3-540-45257-7_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/14.8.726", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015181306"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmbi.2000.4315", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018016237"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/18.suppl_1.s46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026394968"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmbi.1997.0951", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028174721"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(02)00009-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051890836"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(02)00009-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051890836"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/5.18626", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061178979"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539795290477", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880056"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1083156239", 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511790492", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098676015"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "Hidden Markov models (HMMs) are often used for biological sequence annotation. Each sequence element is represented by states with the same label. A sequence should be annotated with the labeling of highest probability. Computing this most probable labeling was shown NP-hard by Lyngs\u00f8 and Pedersen [9]. We improve this result by proving the problem NP-hard for a fixed HMM. High probability labelings are often found by heuristics, such as taking the labeling corresponding to the most probable state path. We introduce an efficient algorithm that computes the most probable labeling for a wide class of HMMs, including models previously used for transmembrane protein topology prediction and coding region detection.", 
        "editor": [
          {
            "familyName": "Jonassen", 
            "givenName": "Inge", 
            "type": "Person"
          }, 
          {
            "familyName": "Kim", 
            "givenName": "Junhyong", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-30219-3_36", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-23018-2", 
            "978-3-540-30219-3"
          ], 
          "name": "Algorithms in Bioinformatics", 
          "type": "Book"
        }, 
        "name": "The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics", 
        "pagination": "426-437", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000399524"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-30219-3_36"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "01e70e0e0ea4c0b5480a9daa993a8a83623aba1b5d8c0e2bd6028d3d20c7951f"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-30219-3_36", 
          "https://app.dimensions.ai/details/publication/pub.1000399524"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:26", 
        "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/0000000363_0000000363/records_70058_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-30219-3_36"
      }
    ]
     

    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-30219-3_36'

    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-30219-3_36'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_36'

    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-30219-3_36'


     

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

    114 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-30219-3_36 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N28ae4986a9d64eb5bbc3ec35d56a8ca1
    4 schema:citation sg:pub.10.1007/978-3-540-45257-7_2
    5 https://app.dimensions.ai/details/publication/pub.1083156239
    6 https://doi.org/10.1006/jmbi.1997.0951
    7 https://doi.org/10.1006/jmbi.2000.4315
    8 https://doi.org/10.1016/s0022-0000(02)00009-0
    9 https://doi.org/10.1017/cbo9780511790492
    10 https://doi.org/10.1093/bioinformatics/14.8.726
    11 https://doi.org/10.1093/bioinformatics/18.suppl_1.s46
    12 https://doi.org/10.1109/5.18626
    13 https://doi.org/10.1137/s0097539795290477
    14 schema:datePublished 2004
    15 schema:datePublishedReg 2004-01-01
    16 schema:description Hidden Markov models (HMMs) are often used for biological sequence annotation. Each sequence element is represented by states with the same label. A sequence should be annotated with the labeling of highest probability. Computing this most probable labeling was shown NP-hard by Lyngsø and Pedersen [9]. We improve this result by proving the problem NP-hard for a fixed HMM. High probability labelings are often found by heuristics, such as taking the labeling corresponding to the most probable state path. We introduce an efficient algorithm that computes the most probable labeling for a wide class of HMMs, including models previously used for transmembrane protein topology prediction and coding region detection.
    17 schema:editor N11c768e9e6ba463d9f7a8f106d28ce8f
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree true
    21 schema:isPartOf Nb796bc50a18647ed9d24cf0742c4075c
    22 schema:name The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics
    23 schema:pagination 426-437
    24 schema:productId N13a0752e8ebf4e199e51824a57906237
    25 N2d24f88834654ee691c20ff12d5226a2
    26 Nbd16c79b98aa4b8cb2d17483e2bd440a
    27 schema:publisher N1d65fb86718840a383e220487556013a
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000399524
    29 https://doi.org/10.1007/978-3-540-30219-3_36
    30 schema:sdDatePublished 2019-04-16T08:26
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher Nd540495d336b4b9ca51a8aba8e8a42e7
    33 schema:url https://link.springer.com/10.1007%2F978-3-540-30219-3_36
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N11c768e9e6ba463d9f7a8f106d28ce8f rdf:first Ncdbc7b84be6a47aaa804c8d43d0eefe0
    38 rdf:rest Nbd3d6070ee604c6c8fe8ca986c7a44e6
    39 N13a0752e8ebf4e199e51824a57906237 schema:name readcube_id
    40 schema:value 01e70e0e0ea4c0b5480a9daa993a8a83623aba1b5d8c0e2bd6028d3d20c7951f
    41 rdf:type schema:PropertyValue
    42 N1d65fb86718840a383e220487556013a schema:location Berlin, Heidelberg
    43 schema:name Springer Berlin Heidelberg
    44 rdf:type schema:Organisation
    45 N28ae4986a9d64eb5bbc3ec35d56a8ca1 rdf:first sg:person.0642141060.90
    46 rdf:rest N6684fbfda4e9408dbfaa12da34118719
    47 N2d24f88834654ee691c20ff12d5226a2 schema:name doi
    48 schema:value 10.1007/978-3-540-30219-3_36
    49 rdf:type schema:PropertyValue
    50 N33f5434bd7a7491cb8e5259306118daf rdf:first sg:person.01041305251.67
    51 rdf:rest rdf:nil
    52 N55df0b5a1e8e4a93bdcf7e31c8d62f0c schema:familyName Kim
    53 schema:givenName Junhyong
    54 rdf:type schema:Person
    55 N6684fbfda4e9408dbfaa12da34118719 rdf:first sg:person.0642727740.54
    56 rdf:rest N33f5434bd7a7491cb8e5259306118daf
    57 Nb796bc50a18647ed9d24cf0742c4075c schema:isbn 978-3-540-23018-2
    58 978-3-540-30219-3
    59 schema:name Algorithms in Bioinformatics
    60 rdf:type schema:Book
    61 Nbd16c79b98aa4b8cb2d17483e2bd440a schema:name dimensions_id
    62 schema:value pub.1000399524
    63 rdf:type schema:PropertyValue
    64 Nbd3d6070ee604c6c8fe8ca986c7a44e6 rdf:first N55df0b5a1e8e4a93bdcf7e31c8d62f0c
    65 rdf:rest rdf:nil
    66 Ncdbc7b84be6a47aaa804c8d43d0eefe0 schema:familyName Jonassen
    67 schema:givenName Inge
    68 rdf:type schema:Person
    69 Nd540495d336b4b9ca51a8aba8e8a42e7 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:person.01041305251.67 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    78 schema:familyName Vinař
    79 schema:givenName Tomáš
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01041305251.67
    81 rdf:type schema:Person
    82 sg:person.0642141060.90 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    83 schema:familyName Brejová
    84 schema:givenName Broňa
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642141060.90
    86 rdf:type schema:Person
    87 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    88 schema:familyName Brown
    89 schema:givenName Daniel G.
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
    91 rdf:type schema:Person
    92 sg:pub.10.1007/978-3-540-45257-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005228610
    93 https://doi.org/10.1007/978-3-540-45257-7_2
    94 rdf:type schema:CreativeWork
    95 https://app.dimensions.ai/details/publication/pub.1083156239 schema:CreativeWork
    96 https://doi.org/10.1006/jmbi.1997.0951 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028174721
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1006/jmbi.2000.4315 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018016237
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/s0022-0000(02)00009-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051890836
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1017/cbo9780511790492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098676015
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1093/bioinformatics/14.8.726 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015181306
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1093/bioinformatics/18.suppl_1.s46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026394968
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/5.18626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061178979
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1137/s0097539795290477 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880056
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    113 schema:name School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
    114 rdf:type schema:Organization
     




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


    ...