Coarse-Grained Parallelization of Distance-Bound Smoothing for the Molecular Conformation Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-12-16

AUTHORS

Narsingh Deo , Paulius Micikevicius

ABSTRACT

Determining the three-dimensional structure of proteins is crucial to efficient drug design and understanding biological processes. One successful method for computing the molecule’s shape relies on the inter-atomic distance bounds provided by the Nucleo-Magnetic Resonance (NMR) spectroscopy. The accuracy of computed structures as well as the time required to obtain them are greatly improved if the gaps between the upper and lower distance-bounds are reduced. These gaps are reduced most effectively by applying the tetrangle inequality, derived from the Cayley-Menger determinant, to all atom-quadruples. However, tetrangle-inequality bound-smoothing is an extremely computation intensive task, requiring O(n4) time for an n-atom molecule. To reduce the computation time, we propose a novel coarse-grained parallel algorithm intended for a Beowulf-type cluster of PCs. The algorithm employs p n/6 processors and requires O(n4/p) time and O(p2) communications. The number of communications is at least an order of magnitude lower than in the earlier parallelizations. Our implementation utilized the processors with at least 59% efficiency (including the communication overhead) — an impressive figure for a nonembarrassingly parallel problem on a cluster of workstations. More... »

PAGES

55-66

References to SciGraph publications

  • 1989-01. Computational experience with an algorithm for tetrangle inequality bound smoothing in BULLETIN OF MATHEMATICAL BIOLOGY
  • 1999-09. Computational experience with a parallel algorithm for tetrangle inequality bound smoothing in BULLETIN OF MATHEMATICAL BIOLOGY
  • 1999. A Coming of Age for Beowulf-Class Computing in EURO-PAR’99 PARALLEL PROCESSING
  • 1989. Tertiary Structure Prediction in PREDICTION OF PROTEIN STRUCTURE AND THE PRINCIPLES OF PROTEIN CONFORMATION
  • Book

    TITLE

    Distributed Computing

    ISBN

    978-3-540-00355-7
    978-3-540-36385-9

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-36385-8_6

    DOI

    http://dx.doi.org/10.1007/3-540-36385-8_6

    DIMENSIONS

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


    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/0202", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Atomic, Molecular, Nuclear, Particle and Plasma Physics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/02", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Physical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Central Florida", 
              "id": "https://www.grid.ac/institutes/grid.170430.1", 
              "name": [
                "School of Electrical Engineering and Computer Science, University of Central Florida, 32816-2362, Orlando, FL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "Narsingh", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Central Florida", 
              "id": "https://www.grid.ac/institutes/grid.170430.1", 
              "name": [
                "School of Electrical Engineering and Computer Science, University of Central Florida, 32816-2362, Orlando, FL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Micikevicius", 
            "givenName": "Paulius", 
            "id": "sg:person.014360625005.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014360625005.02"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-48311-x_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003422453", 
              "https://doi.org/10.1007/3-540-48311-x_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jmbi.1995.0436", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010728475"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0021-9991(77)90112-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021996867"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1006/bulm.1999.0123", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026990963", 
              "https://doi.org/10.1006/bulm.1999.0123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0097-3165(79)90105-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034535688"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/nar/28.1.235", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035055456"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/bip.360291207", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038765900"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-1571-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040468711", 
              "https://doi.org/10.1007/978-1-4613-1571-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-1571-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040468711", 
              "https://doi.org/10.1007/978-1-4613-1571-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02458843", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042695908", 
              "https://doi.org/10.1007/bf02458843"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02458843", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042695908", 
              "https://doi.org/10.1007/bf02458843"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0079-6107(91)90007-f", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050172988"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-7306(08)60458-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050527137"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0033583598003436", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054077673"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0033583598003436", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054077673"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.181.4096.223", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062507831"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0805040", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062854323"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2371222", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069897945"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipps.1999.760545", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094644460"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-12-16", 
        "datePublishedReg": "2002-12-16", 
        "description": "Determining the three-dimensional structure of proteins is crucial to efficient drug design and understanding biological processes. One successful method for computing the molecule\u2019s shape relies on the inter-atomic distance bounds provided by the Nucleo-Magnetic Resonance (NMR) spectroscopy. The accuracy of computed structures as well as the time required to obtain them are greatly improved if the gaps between the upper and lower distance-bounds are reduced. These gaps are reduced most effectively by applying the tetrangle inequality, derived from the Cayley-Menger determinant, to all atom-quadruples. However, tetrangle-inequality bound-smoothing is an extremely computation intensive task, requiring O(n4) time for an n-atom molecule. To reduce the computation time, we propose a novel coarse-grained parallel algorithm intended for a Beowulf-type cluster of PCs. The algorithm employs p n/6 processors and requires O(n4/p) time and O(p2) communications. The number of communications is at least an order of magnitude lower than in the earlier parallelizations. Our implementation utilized the processors with at least 59% efficiency (including the communication overhead) \u2014 an impressive figure for a nonembarrassingly parallel problem on a cluster of workstations.", 
        "editor": [
          {
            "familyName": "Das", 
            "givenName": "Sajal K.", 
            "type": "Person"
          }, 
          {
            "familyName": "Bhattacharya", 
            "givenName": "Swapan", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-36385-8_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-00355-7", 
            "978-3-540-36385-9"
          ], 
          "name": "Distributed Computing", 
          "type": "Book"
        }, 
        "name": "Coarse-Grained Parallelization of Distance-Bound Smoothing for the Molecular Conformation Problem", 
        "pagination": "55-66", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-36385-8_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ea0b05aeca9537bb35ea94216da9b3736f5089b803247e17c5c81231d83e6cfa"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1049129030"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-36385-8_6", 
          "https://app.dimensions.ai/details/publication/pub.1049129030"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:36", 
        "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/0000000346_0000000346/records_99832_00000003.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-36385-8_6"
      }
    ]
     

    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/3-540-36385-8_6'

    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/3-540-36385-8_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36385-8_6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36385-8_6'


     

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

    129 TRIPLES      23 PREDICATES      42 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-36385-8_6 schema:about anzsrc-for:02
    2 anzsrc-for:0202
    3 schema:author N0dc4ea3da03b4c51a58cb52e011ace4b
    4 schema:citation sg:pub.10.1006/bulm.1999.0123
    5 sg:pub.10.1007/3-540-48311-x_6
    6 sg:pub.10.1007/978-1-4613-1571-1_17
    7 sg:pub.10.1007/bf02458843
    8 https://doi.org/10.1002/bip.360291207
    9 https://doi.org/10.1006/jmbi.1995.0436
    10 https://doi.org/10.1016/0021-9991(77)90112-7
    11 https://doi.org/10.1016/0079-6107(91)90007-f
    12 https://doi.org/10.1016/0097-3165(79)90105-5
    13 https://doi.org/10.1016/s0167-7306(08)60458-5
    14 https://doi.org/10.1017/s0033583598003436
    15 https://doi.org/10.1093/nar/28.1.235
    16 https://doi.org/10.1109/ipps.1999.760545
    17 https://doi.org/10.1126/science.181.4096.223
    18 https://doi.org/10.1137/0805040
    19 https://doi.org/10.2307/2371222
    20 schema:datePublished 2002-12-16
    21 schema:datePublishedReg 2002-12-16
    22 schema:description Determining the three-dimensional structure of proteins is crucial to efficient drug design and understanding biological processes. One successful method for computing the molecule’s shape relies on the inter-atomic distance bounds provided by the Nucleo-Magnetic Resonance (NMR) spectroscopy. The accuracy of computed structures as well as the time required to obtain them are greatly improved if the gaps between the upper and lower distance-bounds are reduced. These gaps are reduced most effectively by applying the tetrangle inequality, derived from the Cayley-Menger determinant, to all atom-quadruples. However, tetrangle-inequality bound-smoothing is an extremely computation intensive task, requiring O(n4) time for an n-atom molecule. To reduce the computation time, we propose a novel coarse-grained parallel algorithm intended for a Beowulf-type cluster of PCs. The algorithm employs p n/6 processors and requires O(n4/p) time and O(p2) communications. The number of communications is at least an order of magnitude lower than in the earlier parallelizations. Our implementation utilized the processors with at least 59% efficiency (including the communication overhead) — an impressive figure for a nonembarrassingly parallel problem on a cluster of workstations.
    23 schema:editor N3fde120aad784dd583a429be7148441f
    24 schema:genre chapter
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf Nd31fe4bea6364beda3abcd52378207b5
    28 schema:name Coarse-Grained Parallelization of Distance-Bound Smoothing for the Molecular Conformation Problem
    29 schema:pagination 55-66
    30 schema:productId N7ed06342d32f44b18587be61fd54a1a4
    31 Nd8becb25c4e746bab21190e4136517ad
    32 Neba517ed979a4e14a34ce2eaad518f70
    33 schema:publisher N714d06bf9e434d8ea8ad95ac53857356
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049129030
    35 https://doi.org/10.1007/3-540-36385-8_6
    36 schema:sdDatePublished 2019-04-16T05:36
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher Ne436739271b04cc389d67786e55e35a6
    39 schema:url https://link.springer.com/10.1007%2F3-540-36385-8_6
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset chapters
    42 rdf:type schema:Chapter
    43 N021c2e92b109419b966abd34b9fe91ee rdf:first Nc5c509956cb64263936b9d6791c10863
    44 rdf:rest rdf:nil
    45 N0dc4ea3da03b4c51a58cb52e011ace4b rdf:first sg:person.010274011142.47
    46 rdf:rest Na41e08541f9a461dba10d3c19207f72d
    47 N3fde120aad784dd583a429be7148441f rdf:first N4645548f67e3450b903a9b147bdf04b1
    48 rdf:rest N021c2e92b109419b966abd34b9fe91ee
    49 N4645548f67e3450b903a9b147bdf04b1 schema:familyName Das
    50 schema:givenName Sajal K.
    51 rdf:type schema:Person
    52 N714d06bf9e434d8ea8ad95ac53857356 schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 N7ed06342d32f44b18587be61fd54a1a4 schema:name dimensions_id
    56 schema:value pub.1049129030
    57 rdf:type schema:PropertyValue
    58 Na41e08541f9a461dba10d3c19207f72d rdf:first sg:person.014360625005.02
    59 rdf:rest rdf:nil
    60 Nc5c509956cb64263936b9d6791c10863 schema:familyName Bhattacharya
    61 schema:givenName Swapan
    62 rdf:type schema:Person
    63 Nd31fe4bea6364beda3abcd52378207b5 schema:isbn 978-3-540-00355-7
    64 978-3-540-36385-9
    65 schema:name Distributed Computing
    66 rdf:type schema:Book
    67 Nd8becb25c4e746bab21190e4136517ad schema:name readcube_id
    68 schema:value ea0b05aeca9537bb35ea94216da9b3736f5089b803247e17c5c81231d83e6cfa
    69 rdf:type schema:PropertyValue
    70 Ne436739271b04cc389d67786e55e35a6 schema:name Springer Nature - SN SciGraph project
    71 rdf:type schema:Organization
    72 Neba517ed979a4e14a34ce2eaad518f70 schema:name doi
    73 schema:value 10.1007/3-540-36385-8_6
    74 rdf:type schema:PropertyValue
    75 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Physical Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0202 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Atomic, Molecular, Nuclear, Particle and Plasma Physics
    80 rdf:type schema:DefinedTerm
    81 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
    82 schema:familyName Deo
    83 schema:givenName Narsingh
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    85 rdf:type schema:Person
    86 sg:person.014360625005.02 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
    87 schema:familyName Micikevicius
    88 schema:givenName Paulius
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014360625005.02
    90 rdf:type schema:Person
    91 sg:pub.10.1006/bulm.1999.0123 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026990963
    92 https://doi.org/10.1006/bulm.1999.0123
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/3-540-48311-x_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003422453
    95 https://doi.org/10.1007/3-540-48311-x_6
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-1-4613-1571-1_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040468711
    98 https://doi.org/10.1007/978-1-4613-1571-1_17
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf02458843 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042695908
    101 https://doi.org/10.1007/bf02458843
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1002/bip.360291207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038765900
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1006/jmbi.1995.0436 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010728475
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0021-9991(77)90112-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021996867
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/0079-6107(91)90007-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1050172988
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/0097-3165(79)90105-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034535688
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/s0167-7306(08)60458-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050527137
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1017/s0033583598003436 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054077673
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1093/nar/28.1.235 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035055456
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1109/ipps.1999.760545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094644460
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1126/science.181.4096.223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062507831
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1137/0805040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854323
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.2307/2371222 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069897945
    126 rdf:type schema:CreativeWork
    127 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
    128 schema:name School of Electrical Engineering and Computer Science, University of Central Florida, 32816-2362, Orlando, FL
    129 rdf:type schema:Organization
     




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


    ...