How to Multiply Dynamic Programming Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Christian Höner zu Siederdissen , Ivo L. Hofacker , Peter F. Stadler

ABSTRACT

We develop a theory of algebraic operations over linear grammars that makes it possible to combine simple “atomic” grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple 1-dimensional grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in \({\hbox{\LaTeX}}\) for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler. http://www.bioinf.uni-leipzig.de/Software/gramprod/ More... »

PAGES

82-93

References to SciGraph publications

  • 2005-12. Versatile and declarative dynamic programming using pair algebras in BMC BIOINFORMATICS
  • 2002-09-02. Algebraic Dynamic Programming in ALGEBRAIC METHODOLOGY AND SOFTWARE TECHNOLOGY
  • 2007-12. Progressive multiple sequence alignments from triplets in BMC BIOINFORMATICS
  • Book

    TITLE

    Advances in Bioinformatics and Computational Biology

    ISBN

    978-3-319-02623-7
    978-3-319-02624-4

    Author Affiliations

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-02624-4_8

    DOI

    http://dx.doi.org/10.1007/978-3-319-02624-4_8

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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 Vienna", 
              "id": "https://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Dept. Theoretical Chemistry, Univ. Vienna, W\u00e4hringerstr. 17, Wien, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Siederdissen", 
            "givenName": "Christian H\u00f6ner zu", 
            "id": "sg:person.010213207253.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010213207253.25"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Vienna", 
              "id": "https://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Dept. Theoretical Chemistry, Univ. Vienna, W\u00e4hringerstr. 17, Wien, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hofacker", 
            "givenName": "Ivo L.", 
            "id": "sg:person.01222322364.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01222322364.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Dept. Computer Science, and Interdisciplinary Center for Bioinformatics, Univ. Leipzig, H\u00e4rtelstr. 16-18, Leipzig, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Stadler", 
            "givenName": "Peter F.", 
            "id": "sg:person.0664150133.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0664150133.70"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/2500365.2500601", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000304393"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-2836(70)90057-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021169618"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1291151.1291199", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023300338"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-2836(82)90398-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025042064"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-6-224", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025667233", 
              "https://doi.org/10.1186/1471-2105-6-224"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-8-254", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026948542", 
              "https://doi.org/10.1186/1471-2105-8-254"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-5193(86)80112-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032371696"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.86.12.4412", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033409872"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45719-4_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034443749", 
              "https://doi.org/10.1007/3-540-45719-4_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45719-4_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034443749", 
              "https://doi.org/10.1007/3-540-45719-4_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1863543.1863582", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036846343"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.scico.2003.12.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040539922"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1163/221058211x570358", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051524678"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1163/221058211x570358", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051524678"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1089/106652701300312931", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059204879"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0145048", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062840393"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0219720004000831", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063004573"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013", 
        "datePublishedReg": "2013-01-01", 
        "description": "We develop a theory of algebraic operations over linear grammars that makes it possible to combine simple \u201catomic\u201d grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple 1-dimensional grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in \\({\\hbox{\\LaTeX}}\\) for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler. http://www.bioinf.uni-leipzig.de/Software/gramprod/", 
        "editor": [
          {
            "familyName": "Setubal", 
            "givenName": "Jo\u00e3o C.", 
            "type": "Person"
          }, 
          {
            "familyName": "Almeida", 
            "givenName": "Nalvo F.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-02624-4_8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7580451", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-319-02623-7", 
            "978-3-319-02624-4"
          ], 
          "name": "Advances in Bioinformatics and Computational Biology", 
          "type": "Book"
        }, 
        "name": "How to Multiply Dynamic Programming Algorithms", 
        "pagination": "82-93", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-02624-4_8"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "fc35652b5195ec01664678efd30faf3ff131841db67af14533ef841e51377a69"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1052948637"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-02624-4_8", 
          "https://app.dimensions.ai/details/publication/pub.1052948637"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T11:38", 
        "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_8660_00000276.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-02624-4_8"
      }
    ]
     

    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-319-02624-4_8'

    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-319-02624-4_8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-02624-4_8'

    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-319-02624-4_8'


     

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

    136 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-02624-4_8 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N43e20ad22038461ab79afdc1f8ad40f1
    4 schema:citation sg:pub.10.1007/3-540-45719-4_24
    5 sg:pub.10.1186/1471-2105-6-224
    6 sg:pub.10.1186/1471-2105-8-254
    7 https://doi.org/10.1016/0022-2836(70)90057-4
    8 https://doi.org/10.1016/0022-2836(82)90398-9
    9 https://doi.org/10.1016/j.scico.2003.12.005
    10 https://doi.org/10.1016/s0022-5193(86)80112-6
    11 https://doi.org/10.1073/pnas.86.12.4412
    12 https://doi.org/10.1089/106652701300312931
    13 https://doi.org/10.1137/0145048
    14 https://doi.org/10.1142/s0219720004000831
    15 https://doi.org/10.1145/1291151.1291199
    16 https://doi.org/10.1145/1863543.1863582
    17 https://doi.org/10.1145/2500365.2500601
    18 https://doi.org/10.1163/221058211x570358
    19 schema:datePublished 2013
    20 schema:datePublishedReg 2013-01-01
    21 schema:description We develop a theory of algebraic operations over linear grammars that makes it possible to combine simple “atomic” grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple 1-dimensional grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in \({\hbox{\LaTeX}}\) for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler. http://www.bioinf.uni-leipzig.de/Software/gramprod/
    22 schema:editor Nde79413ccdb34f1e96d63a3f83c960d8
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N42adfec8fc7e4f54841ed82b0b67154f
    27 schema:name How to Multiply Dynamic Programming Algorithms
    28 schema:pagination 82-93
    29 schema:productId N42b4c201948e4ca08b1dda6a1c0689f5
    30 Ne63183ab6fcc4a0d83edab5d0cffe1a5
    31 Nf38aead0ce6441139ec197e48cfc20a1
    32 schema:publisher Ned1fd3f54d174e12b0ffe7469286c0cd
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052948637
    34 https://doi.org/10.1007/978-3-319-02624-4_8
    35 schema:sdDatePublished 2019-04-15T11:38
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher N4e20a408091a47528951da7e943fde44
    38 schema:url http://link.springer.com/10.1007/978-3-319-02624-4_8
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N0c4268c47c62439d8411fc1d6219af86 schema:familyName Setubal
    43 schema:givenName João C.
    44 rdf:type schema:Person
    45 N3ec1f0d914584d1c8b1b547961782ee8 schema:familyName Almeida
    46 schema:givenName Nalvo F.
    47 rdf:type schema:Person
    48 N42adfec8fc7e4f54841ed82b0b67154f schema:isbn 978-3-319-02623-7
    49 978-3-319-02624-4
    50 schema:name Advances in Bioinformatics and Computational Biology
    51 rdf:type schema:Book
    52 N42b4c201948e4ca08b1dda6a1c0689f5 schema:name readcube_id
    53 schema:value fc35652b5195ec01664678efd30faf3ff131841db67af14533ef841e51377a69
    54 rdf:type schema:PropertyValue
    55 N43e20ad22038461ab79afdc1f8ad40f1 rdf:first sg:person.010213207253.25
    56 rdf:rest N60acc9b1a7f0437397bde01805a0473b
    57 N4e20a408091a47528951da7e943fde44 schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 N60acc9b1a7f0437397bde01805a0473b rdf:first sg:person.01222322364.52
    60 rdf:rest N684ce77b021441b887e96878a3912b94
    61 N684ce77b021441b887e96878a3912b94 rdf:first sg:person.0664150133.70
    62 rdf:rest rdf:nil
    63 Nae6867c532fc4d8986f04aa093fc07a7 rdf:first N3ec1f0d914584d1c8b1b547961782ee8
    64 rdf:rest rdf:nil
    65 Nde79413ccdb34f1e96d63a3f83c960d8 rdf:first N0c4268c47c62439d8411fc1d6219af86
    66 rdf:rest Nae6867c532fc4d8986f04aa093fc07a7
    67 Ne63183ab6fcc4a0d83edab5d0cffe1a5 schema:name doi
    68 schema:value 10.1007/978-3-319-02624-4_8
    69 rdf:type schema:PropertyValue
    70 Ned1fd3f54d174e12b0ffe7469286c0cd schema:location Cham
    71 schema:name Springer International Publishing
    72 rdf:type schema:Organisation
    73 Nf0e1a6cb4e4b47718a8d66df3dce119c schema:name Dept. Computer Science, and Interdisciplinary Center for Bioinformatics, Univ. Leipzig, Härtelstr. 16-18, Leipzig, Germany
    74 rdf:type schema:Organization
    75 Nf38aead0ce6441139ec197e48cfc20a1 schema:name dimensions_id
    76 schema:value pub.1052948637
    77 rdf:type schema:PropertyValue
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Artificial Intelligence and Image Processing
    83 rdf:type schema:DefinedTerm
    84 sg:grant.7580451 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-319-02624-4_8
    85 rdf:type schema:MonetaryGrant
    86 sg:person.010213207253.25 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
    87 schema:familyName Siederdissen
    88 schema:givenName Christian Höner zu
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010213207253.25
    90 rdf:type schema:Person
    91 sg:person.01222322364.52 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
    92 schema:familyName Hofacker
    93 schema:givenName Ivo L.
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01222322364.52
    95 rdf:type schema:Person
    96 sg:person.0664150133.70 schema:affiliation Nf0e1a6cb4e4b47718a8d66df3dce119c
    97 schema:familyName Stadler
    98 schema:givenName Peter F.
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0664150133.70
    100 rdf:type schema:Person
    101 sg:pub.10.1007/3-540-45719-4_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034443749
    102 https://doi.org/10.1007/3-540-45719-4_24
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1186/1471-2105-6-224 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025667233
    105 https://doi.org/10.1186/1471-2105-6-224
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1186/1471-2105-8-254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026948542
    108 https://doi.org/10.1186/1471-2105-8-254
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/0022-2836(70)90057-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021169618
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/0022-2836(82)90398-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025042064
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/j.scico.2003.12.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040539922
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1016/s0022-5193(86)80112-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032371696
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1073/pnas.86.12.4412 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033409872
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1089/106652701300312931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059204879
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1137/0145048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062840393
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1142/s0219720004000831 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063004573
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/1291151.1291199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023300338
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1145/1863543.1863582 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036846343
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/2500365.2500601 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000304393
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1163/221058211x570358 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051524678
    133 rdf:type schema:CreativeWork
    134 https://www.grid.ac/institutes/grid.10420.37 schema:alternateName University of Vienna
    135 schema:name Dept. Theoretical Chemistry, Univ. Vienna, Währingerstr. 17, Wien, Austria
    136 rdf:type schema:Organization
     




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


    ...