Computational experience with a parallel algorithm for tetrangle inequality bound smoothing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-09

AUTHORS

Kumar Rajan, Narsingh Deo

ABSTRACT

Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the 2(n(n-1)) atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the 2(n(n-1)) pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and infinity. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality--the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley-Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the (4n) quadruples requires O(n4) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n3 log n) time on a REW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with O(log(n)n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed. More... »

PAGES

987-1008

References to SciGraph publications

  • 1989. Computational experience with an algorithm for tetrangle inequality bound smoothing in BULLETIN OF MATHEMATICAL BIOLOGY
  • 1983. The theory and practice of distance geometry in BULLETIN OF MATHEMATICAL BIOLOGY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1006/bulm.1999.0123

    DOI

    http://dx.doi.org/10.1006/bulm.1999.0123

    DIMENSIONS

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

    PUBMED

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


    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"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Algorithms", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Magnetic Resonance Spectroscopy", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Molecular Conformation", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Central Florida", 
              "id": "https://www.grid.ac/institutes/grid.170430.1", 
              "name": [
                "School of Computer Science, University of Central Florida, 32816-2362, Orlando, FL, USA", 
                "15420, Plantation Oaks Blvd, Apt. 11, FL-33647, Tampa, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rajan", 
            "givenName": "Kumar", 
            "id": "sg:person.01141643252.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01141643252.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Central Florida", 
              "id": "https://www.grid.ac/institutes/grid.170430.1", 
              "name": [
                "School of Computer Science, University of Central Florida, 32816-2362, Orlando, FL, USA"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0021-9991(77)90112-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021996867"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-2836(88)90589-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024383699"
            ], 
            "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.1016/0166-218x(88)90009-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043246100"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(80)90236-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045925802"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(80)90236-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045925802"
            ], 
            "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.1016/0012-365x(83)90045-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053626768"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0033583500003966", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054090072"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0033583500003966", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054090072"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1016/s0092-8240(83)80020-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054614582", 
              "https://doi.org/10.1016/s0092-8240(83)80020-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1016/s0092-8240(89)80055-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054614959", 
              "https://doi.org/10.1016/s0092-8240(89)80055-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1021/bi980112r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1055215464"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1021/bi980112r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1055215464"
            ], 
            "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.1137/s1052623495283024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062883493"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1999-09", 
        "datePublishedReg": "1999-09-01", 
        "description": "Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the 2(n(n-1)) atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the 2(n(n-1)) pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and infinity. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality--the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley-Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the (4n) quadruples requires O(n4) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n3 log n) time on a REW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with O(log(n)n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1006/bulm.1999.0123", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1018370", 
            "issn": [
              "0092-8240", 
              "1522-9602"
            ], 
            "name": "Bulletin of Mathematical Biology", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "61"
          }
        ], 
        "name": "Computational experience with a parallel algorithm for tetrangle inequality bound smoothing", 
        "pagination": "987-1008", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "8094323092bc4c339b64f348dcff28603984c322e158c974aee1eacd946e9bd6"
            ]
          }, 
          {
            "name": "pubmed_id", 
            "type": "PropertyValue", 
            "value": [
              "17886753"
            ]
          }, 
          {
            "name": "nlm_unique_id", 
            "type": "PropertyValue", 
            "value": [
              "0401404"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1006/bulm.1999.0123"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1026990963"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1006/bulm.1999.0123", 
          "https://app.dimensions.ai/details/publication/pub.1026990963"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T21:40", 
        "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_8687_00000532.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1006%2Fbulm.1999.0123"
      }
    ]
     

    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.1006/bulm.1999.0123'

    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.1006/bulm.1999.0123'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1006/bulm.1999.0123'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1006/bulm.1999.0123'


     

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

    130 TRIPLES      21 PREDICATES      45 URIs      24 LITERALS      12 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1006/bulm.1999.0123 schema:about N72cc629954814e0581b3631a4bdc2dec
    2 N9e910bdcba274beaaf8816003be26f4b
    3 Nfe3619332e5740b3b3dca2c237b56dc4
    4 anzsrc-for:02
    5 anzsrc-for:0202
    6 schema:author Nc3c8f59104ad477cb64ccce742633b84
    7 schema:citation sg:pub.10.1016/s0092-8240(83)80020-2
    8 sg:pub.10.1016/s0092-8240(89)80055-2
    9 https://doi.org/10.1016/0012-365x(80)90236-8
    10 https://doi.org/10.1016/0012-365x(83)90045-6
    11 https://doi.org/10.1016/0021-9991(77)90112-7
    12 https://doi.org/10.1016/0022-2836(88)90589-x
    13 https://doi.org/10.1016/0097-3165(79)90105-5
    14 https://doi.org/10.1016/0166-218x(88)90009-1
    15 https://doi.org/10.1016/s0167-7306(08)60458-5
    16 https://doi.org/10.1017/s0033583500003966
    17 https://doi.org/10.1021/bi980112r
    18 https://doi.org/10.1137/0805040
    19 https://doi.org/10.1137/s1052623495283024
    20 schema:datePublished 1999-09
    21 schema:datePublishedReg 1999-09-01
    22 schema:description Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the 2(n(n-1)) atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the 2(n(n-1)) pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and infinity. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality--the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley-Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the (4n) quadruples requires O(n4) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n3 log n) time on a REW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with O(log(n)n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed.
    23 schema:genre research_article
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N8bd220a0878946b8a00953e71cf2f45a
    27 Ndfcf8c9d4bf04e64ae054e2110bec9cd
    28 sg:journal.1018370
    29 schema:name Computational experience with a parallel algorithm for tetrangle inequality bound smoothing
    30 schema:pagination 987-1008
    31 schema:productId N269064abc43a48d690ec08128af6ccfd
    32 N7a42712e5d8242c58a281eebfd9b70d3
    33 N921f5791a23845dfaffa2e4036e1afb9
    34 Na1a6f3b7c6bc4531a8972f733da4b683
    35 Nae434bf34f9a4dc7b24d88b914245fe3
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026990963
    37 https://doi.org/10.1006/bulm.1999.0123
    38 schema:sdDatePublished 2019-04-10T21:40
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N5f2d5583b42a4b6dbc9f74b92a119cbb
    41 schema:url http://link.springer.com/10.1006%2Fbulm.1999.0123
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N10e1543aa0df4e11b98aacbb11901bb2 rdf:first sg:person.010274011142.47
    46 rdf:rest rdf:nil
    47 N269064abc43a48d690ec08128af6ccfd schema:name dimensions_id
    48 schema:value pub.1026990963
    49 rdf:type schema:PropertyValue
    50 N5f2d5583b42a4b6dbc9f74b92a119cbb schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N72cc629954814e0581b3631a4bdc2dec schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    53 schema:name Magnetic Resonance Spectroscopy
    54 rdf:type schema:DefinedTerm
    55 N7a42712e5d8242c58a281eebfd9b70d3 schema:name pubmed_id
    56 schema:value 17886753
    57 rdf:type schema:PropertyValue
    58 N8bd220a0878946b8a00953e71cf2f45a schema:issueNumber 5
    59 rdf:type schema:PublicationIssue
    60 N921f5791a23845dfaffa2e4036e1afb9 schema:name readcube_id
    61 schema:value 8094323092bc4c339b64f348dcff28603984c322e158c974aee1eacd946e9bd6
    62 rdf:type schema:PropertyValue
    63 N9e910bdcba274beaaf8816003be26f4b schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    64 schema:name Algorithms
    65 rdf:type schema:DefinedTerm
    66 Na1a6f3b7c6bc4531a8972f733da4b683 schema:name doi
    67 schema:value 10.1006/bulm.1999.0123
    68 rdf:type schema:PropertyValue
    69 Nae434bf34f9a4dc7b24d88b914245fe3 schema:name nlm_unique_id
    70 schema:value 0401404
    71 rdf:type schema:PropertyValue
    72 Nc3c8f59104ad477cb64ccce742633b84 rdf:first sg:person.01141643252.87
    73 rdf:rest N10e1543aa0df4e11b98aacbb11901bb2
    74 Ndfcf8c9d4bf04e64ae054e2110bec9cd schema:volumeNumber 61
    75 rdf:type schema:PublicationVolume
    76 Nfe3619332e5740b3b3dca2c237b56dc4 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    77 schema:name Molecular Conformation
    78 rdf:type schema:DefinedTerm
    79 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Physical Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0202 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Atomic, Molecular, Nuclear, Particle and Plasma Physics
    84 rdf:type schema:DefinedTerm
    85 sg:journal.1018370 schema:issn 0092-8240
    86 1522-9602
    87 schema:name Bulletin of Mathematical Biology
    88 rdf:type schema:Periodical
    89 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
    90 schema:familyName Deo
    91 schema:givenName Narsingh
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    93 rdf:type schema:Person
    94 sg:person.01141643252.87 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
    95 schema:familyName Rajan
    96 schema:givenName Kumar
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01141643252.87
    98 rdf:type schema:Person
    99 sg:pub.10.1016/s0092-8240(83)80020-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054614582
    100 https://doi.org/10.1016/s0092-8240(83)80020-2
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1016/s0092-8240(89)80055-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054614959
    103 https://doi.org/10.1016/s0092-8240(89)80055-2
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0012-365x(80)90236-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045925802
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0012-365x(83)90045-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053626768
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/0021-9991(77)90112-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021996867
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/0022-2836(88)90589-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1024383699
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/0097-3165(79)90105-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034535688
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/0166-218x(88)90009-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043246100
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/s0167-7306(08)60458-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050527137
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1017/s0033583500003966 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054090072
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1021/bi980112r schema:sameAs https://app.dimensions.ai/details/publication/pub.1055215464
    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.1137/s1052623495283024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883493
    126 rdf:type schema:CreativeWork
    127 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
    128 schema:name 15420, Plantation Oaks Blvd, Apt. 11, FL-33647, Tampa, USA
    129 School of Computer Science, University of Central Florida, 32816-2362, Orlando, FL, USA
    130 rdf:type schema:Organization
     




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


    ...