3-Points Relationship Based Parallel Algorithm for Minimum Ultrametric Tree Construction View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Kun-Ming Yu , Jiayi Zhou , Chun-Yuan Lin , Chuan Yi Tang

ABSTRACT

To construct an evolutionary tree is an important topic in computational biology. An evolutionary tree can symbolize the relationship and histories for a set of species. There are many models had been proposed to resolve these problems. However, most of them are NP-hard problem. Ultrametric tree is one of the most popular models, it is used by a well-accepted tree construction method–Unweighted Pair Group Method with Arithmetic Mean, which is widely used by biologists to observe the relationship among species. However, it is a heuristic algorithm. In this paper, we proposed a 3-Points relationship (3PR) based parallel algorithm to solve this problem. 3PR is a relationship between distance matrix and constructed evolutionary trees. The main concept is for any triplet species, two species closer to each other in distance matrix should be closer to each other in evolutionary tree. Then we combined this property and branch-and-bound strategy to reduce the computation time to obtain the optimal solution. Moreover, we put the lower ranked path which is determined by3PR to delay bound pool (DBP) to accelerate the algorithm execution. DBP is a mechanism which can store the lower ranked path and can be helping algorithm to find a better bounding values speedily. The experimental results show that our proposed algorithm can reduce the computation time compared with algorithm without 3PR. Moreover, it also shows 3PR can reduce the computation time when number of computing nodes increasing. More... »

PAGES

615-622

References to SciGraph publications

  • 1999-07. Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 1995-02. A robust model for finding optimal evolutionary trees in ALGORITHMICA
  • 2006. An Efficient Parallel Algorithm for Ultrametric Tree Construction Based on 3PR in FRONTIERS OF HIGH PERFORMANCE COMPUTING AND NETWORKING – ISPA 2006 WORKSHOPS
  • 1988-06. A randomized parallel branch-and-bound algorithm in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • Book

    TITLE

    Parallel Computing Technologies

    ISBN

    978-3-540-73939-5
    978-3-540-73940-1

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-73940-1_62

    DOI

    http://dx.doi.org/10.1007/978-3-540-73940-1_62

    DIMENSIONS

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


    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": "Chung Hua University", 
              "id": "https://www.grid.ac/institutes/grid.411655.2", 
              "name": [
                "Department of Computer Science and Information Engineering, Chung Hua University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yu", 
            "givenName": "Kun-Ming", 
            "id": "sg:person.015566066077.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015566066077.39"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Chung Hua University", 
              "id": "https://www.grid.ac/institutes/grid.411655.2", 
              "name": [
                "Institute of Engineering Science, Chung Hua University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhou", 
            "givenName": "Jiayi", 
            "id": "sg:person.016405705547.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016405705547.11"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Institute of Molecular and Cellular Biology, National Tsing Hua University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Chun-Yuan", 
            "id": "sg:person.0665540554.26", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0665540554.26"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Department of Computer Science, National Tsing Hua University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tang", 
            "givenName": "Chuan Yi", 
            "id": "sg:person.01312526135.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01188585", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004227195", 
              "https://doi.org/10.1007/bf01188585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01188585", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004227195", 
              "https://doi.org/10.1007/bf01188585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(88)90090-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012715551"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0025-5564(82)90027-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013420601"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11942634_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025066797", 
              "https://doi.org/10.1007/11942634_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11942634_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025066797", 
              "https://doi.org/10.1007/11942634_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1009885610075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044701682", 
              "https://doi.org/10.1023/a:1009885610075"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02427853", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052057361", 
              "https://doi.org/10.1007/bf02427853"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02427853", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052057361", 
              "https://doi.org/10.1007/bf02427853"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.1736360", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062503559"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.1840702", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062509890"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.14.4.699", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064726998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511574931", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098674485"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "To construct an evolutionary tree is an important topic in computational biology. An evolutionary tree can symbolize the relationship and histories for a set of species. There are many models had been proposed to resolve these problems. However, most of them are NP-hard problem. Ultrametric tree is one of the most popular models, it is used by a well-accepted tree construction method\u2013Unweighted Pair Group Method with Arithmetic Mean, which is widely used by biologists to observe the relationship among species. However, it is a heuristic algorithm. In this paper, we proposed a 3-Points relationship (3PR) based parallel algorithm to solve this problem. 3PR is a relationship between distance matrix and constructed evolutionary trees. The main concept is for any triplet species, two species closer to each other in distance matrix should be closer to each other in evolutionary tree. Then we combined this property and branch-and-bound strategy to reduce the computation time to obtain the optimal solution. Moreover, we put the lower ranked path which is determined by3PR to delay bound pool (DBP) to accelerate the algorithm execution. DBP is a mechanism which can store the lower ranked path and can be helping algorithm to find a better bounding values speedily. The experimental results show that our proposed algorithm can reduce the computation time compared with algorithm without 3PR. Moreover, it also shows 3PR can reduce the computation time when number of computing nodes increasing.", 
        "editor": [
          {
            "familyName": "Malyshkin", 
            "givenName": "Victor", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-73940-1_62", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-73939-5", 
            "978-3-540-73940-1"
          ], 
          "name": "Parallel Computing Technologies", 
          "type": "Book"
        }, 
        "name": "3-Points Relationship Based Parallel Algorithm for Minimum Ultrametric Tree Construction", 
        "pagination": "615-622", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-73940-1_62"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f1b03ff72d4c9633b42f8acd6414068f866a7f779a2719fa5b2b13c570ba0e1a"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1050736258"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-73940-1_62", 
          "https://app.dimensions.ai/details/publication/pub.1050736258"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:27", 
        "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/0000000345_0000000345/records_64117_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-73940-1_62"
      }
    ]
     

    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-73940-1_62'

    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-73940-1_62'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73940-1_62'

    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-73940-1_62'


     

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

    126 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-73940-1_62 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N7c6dd182229240f1a574687447a9ea7a
    4 schema:citation sg:pub.10.1007/11942634_23
    5 sg:pub.10.1007/bf01188585
    6 sg:pub.10.1007/bf02427853
    7 sg:pub.10.1023/a:1009885610075
    8 https://doi.org/10.1016/0020-0190(88)90090-7
    9 https://doi.org/10.1016/0025-5564(82)90027-x
    10 https://doi.org/10.1017/cbo9780511574931
    11 https://doi.org/10.1126/science.1736360
    12 https://doi.org/10.1126/science.1840702
    13 https://doi.org/10.1287/opre.14.4.699
    14 schema:datePublished 2007
    15 schema:datePublishedReg 2007-01-01
    16 schema:description To construct an evolutionary tree is an important topic in computational biology. An evolutionary tree can symbolize the relationship and histories for a set of species. There are many models had been proposed to resolve these problems. However, most of them are NP-hard problem. Ultrametric tree is one of the most popular models, it is used by a well-accepted tree construction method–Unweighted Pair Group Method with Arithmetic Mean, which is widely used by biologists to observe the relationship among species. However, it is a heuristic algorithm. In this paper, we proposed a 3-Points relationship (3PR) based parallel algorithm to solve this problem. 3PR is a relationship between distance matrix and constructed evolutionary trees. The main concept is for any triplet species, two species closer to each other in distance matrix should be closer to each other in evolutionary tree. Then we combined this property and branch-and-bound strategy to reduce the computation time to obtain the optimal solution. Moreover, we put the lower ranked path which is determined by3PR to delay bound pool (DBP) to accelerate the algorithm execution. DBP is a mechanism which can store the lower ranked path and can be helping algorithm to find a better bounding values speedily. The experimental results show that our proposed algorithm can reduce the computation time compared with algorithm without 3PR. Moreover, it also shows 3PR can reduce the computation time when number of computing nodes increasing.
    17 schema:editor N647315bcb22d48c98d621e7a097a2e4f
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Nae77c57d2f5a4caa8eda552e7ced3b29
    22 schema:name 3-Points Relationship Based Parallel Algorithm for Minimum Ultrametric Tree Construction
    23 schema:pagination 615-622
    24 schema:productId N0e44d07537c14b24bc64d7d422ea1892
    25 N2bab5b773f92487188e49530a39f478c
    26 N8cc80dc2ab8b480aa4a158b672b4ddbc
    27 schema:publisher Nf0fe6b838d724c7f85b5933897aebaf5
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050736258
    29 https://doi.org/10.1007/978-3-540-73940-1_62
    30 schema:sdDatePublished 2019-04-16T05:27
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N8c0d7f1059074b5a94827d0f21d57d85
    33 schema:url https://link.springer.com/10.1007%2F978-3-540-73940-1_62
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N072baebb868846e7b28bb21225a76d93 rdf:first sg:person.01312526135.27
    38 rdf:rest rdf:nil
    39 N0e44d07537c14b24bc64d7d422ea1892 schema:name doi
    40 schema:value 10.1007/978-3-540-73940-1_62
    41 rdf:type schema:PropertyValue
    42 N2bab5b773f92487188e49530a39f478c schema:name dimensions_id
    43 schema:value pub.1050736258
    44 rdf:type schema:PropertyValue
    45 N3997f43494ec424f8b313bdba5a471a4 rdf:first sg:person.0665540554.26
    46 rdf:rest N072baebb868846e7b28bb21225a76d93
    47 N647315bcb22d48c98d621e7a097a2e4f rdf:first Nedd8e98b5167409ebc64f630c328066a
    48 rdf:rest rdf:nil
    49 N7c6dd182229240f1a574687447a9ea7a rdf:first sg:person.015566066077.39
    50 rdf:rest N93e3a4d1df534de9884bb555703dbfde
    51 N8c0d7f1059074b5a94827d0f21d57d85 schema:name Springer Nature - SN SciGraph project
    52 rdf:type schema:Organization
    53 N8cc80dc2ab8b480aa4a158b672b4ddbc schema:name readcube_id
    54 schema:value f1b03ff72d4c9633b42f8acd6414068f866a7f779a2719fa5b2b13c570ba0e1a
    55 rdf:type schema:PropertyValue
    56 N93e3a4d1df534de9884bb555703dbfde rdf:first sg:person.016405705547.11
    57 rdf:rest N3997f43494ec424f8b313bdba5a471a4
    58 Nae77c57d2f5a4caa8eda552e7ced3b29 schema:isbn 978-3-540-73939-5
    59 978-3-540-73940-1
    60 schema:name Parallel Computing Technologies
    61 rdf:type schema:Book
    62 Nedd8e98b5167409ebc64f630c328066a schema:familyName Malyshkin
    63 schema:givenName Victor
    64 rdf:type schema:Person
    65 Nf0fe6b838d724c7f85b5933897aebaf5 schema:location Berlin, Heidelberg
    66 schema:name Springer Berlin Heidelberg
    67 rdf:type schema:Organisation
    68 Nfd52cbef82614aeab512d002d24c2316 schema:name Institute of Molecular and Cellular Biology, National Tsing Hua University
    69 rdf:type schema:Organization
    70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information and Computing Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Computation Theory and Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    77 schema:familyName Tang
    78 schema:givenName Chuan Yi
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
    80 rdf:type schema:Person
    81 sg:person.015566066077.39 schema:affiliation https://www.grid.ac/institutes/grid.411655.2
    82 schema:familyName Yu
    83 schema:givenName Kun-Ming
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015566066077.39
    85 rdf:type schema:Person
    86 sg:person.016405705547.11 schema:affiliation https://www.grid.ac/institutes/grid.411655.2
    87 schema:familyName Zhou
    88 schema:givenName Jiayi
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016405705547.11
    90 rdf:type schema:Person
    91 sg:person.0665540554.26 schema:affiliation Nfd52cbef82614aeab512d002d24c2316
    92 schema:familyName Lin
    93 schema:givenName Chun-Yuan
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0665540554.26
    95 rdf:type schema:Person
    96 sg:pub.10.1007/11942634_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025066797
    97 https://doi.org/10.1007/11942634_23
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/bf01188585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004227195
    100 https://doi.org/10.1007/bf01188585
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/bf02427853 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052057361
    103 https://doi.org/10.1007/bf02427853
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1023/a:1009885610075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044701682
    106 https://doi.org/10.1023/a:1009885610075
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/0020-0190(88)90090-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012715551
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/0025-5564(82)90027-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013420601
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1017/cbo9780511574931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098674485
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1126/science.1736360 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062503559
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1126/science.1840702 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062509890
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1287/opre.14.4.699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726998
    119 rdf:type schema:CreativeWork
    120 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
    121 schema:name Department of Computer Science, National Tsing Hua University
    122 rdf:type schema:Organization
    123 https://www.grid.ac/institutes/grid.411655.2 schema:alternateName Chung Hua University
    124 schema:name Department of Computer Science and Information Engineering, Chung Hua University
    125 Institute of Engineering Science, Chung Hua University
    126 rdf:type schema:Organization
     




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


    ...