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 N8370d77624654ff399d28c0ae17e0030
    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 N62c1441172024917a277e336785d9157
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree true
    21 schema:isPartOf Nd88b1eeed68249018974f2901fa3d3e1
    22 schema:name The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics
    23 schema:pagination 426-437
    24 schema:productId N0364c960b2474d1ab3cff89f64d4e010
    25 N198ede3f42ba469e9663f35d84bc42c4
    26 Na7592138aac347a7b387a94ebd168d72
    27 schema:publisher N8726af6afe3041d4b61e48344294f05e
    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 N0f9f07d5c7274e2aaa1d195bbcdf545e
    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 N0364c960b2474d1ab3cff89f64d4e010 schema:name doi
    38 schema:value 10.1007/978-3-540-30219-3_36
    39 rdf:type schema:PropertyValue
    40 N0f9f07d5c7274e2aaa1d195bbcdf545e schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N198ede3f42ba469e9663f35d84bc42c4 schema:name readcube_id
    43 schema:value 01e70e0e0ea4c0b5480a9daa993a8a83623aba1b5d8c0e2bd6028d3d20c7951f
    44 rdf:type schema:PropertyValue
    45 N53e95bd1f2fa4896936390d0d9bf2b4d schema:familyName Kim
    46 schema:givenName Junhyong
    47 rdf:type schema:Person
    48 N595677b4f8d042b28e15456038d6c09b rdf:first sg:person.01041305251.67
    49 rdf:rest rdf:nil
    50 N62c1441172024917a277e336785d9157 rdf:first Ndfcce982d5c740ba9c0cc2ae1f22c998
    51 rdf:rest Nbffcba72ad744e8b93bac66b14dcbc41
    52 N8370d77624654ff399d28c0ae17e0030 rdf:first sg:person.0642141060.90
    53 rdf:rest Nc97028c6e2f140ab8dfc750d0e62832c
    54 N8726af6afe3041d4b61e48344294f05e schema:location Berlin, Heidelberg
    55 schema:name Springer Berlin Heidelberg
    56 rdf:type schema:Organisation
    57 Na7592138aac347a7b387a94ebd168d72 schema:name dimensions_id
    58 schema:value pub.1000399524
    59 rdf:type schema:PropertyValue
    60 Nbffcba72ad744e8b93bac66b14dcbc41 rdf:first N53e95bd1f2fa4896936390d0d9bf2b4d
    61 rdf:rest rdf:nil
    62 Nc97028c6e2f140ab8dfc750d0e62832c rdf:first sg:person.0642727740.54
    63 rdf:rest N595677b4f8d042b28e15456038d6c09b
    64 Nd88b1eeed68249018974f2901fa3d3e1 schema:isbn 978-3-540-23018-2
    65 978-3-540-30219-3
    66 schema:name Algorithms in Bioinformatics
    67 rdf:type schema:Book
    68 Ndfcce982d5c740ba9c0cc2ae1f22c998 schema:familyName Jonassen
    69 schema:givenName Inge
    70 rdf:type schema:Person
    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)


    ...