An Efficient Parallel Algorithm for Ultrametric Tree Construction Based on 3PR View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

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

ABSTRACT

In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average. More... »

PAGES

215-220

References to SciGraph publications

Book

TITLE

Frontiers of High Performance Computing and Networking – ISPA 2006 Workshops

ISBN

978-3-540-49860-5
978-3-540-49862-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11942634_23

DOI

http://dx.doi.org/10.1007/11942634_23

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Chung Hua University", 
          "id": "https://www.grid.ac/institutes/grid.411655.2", 
          "name": [
            "Department of 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, 300, Hsinchu, Taiwan, R.O.C"
          ], 
          "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": "https://doi.org/10.1093/bioinformatics/12.4.357", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000618136"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0025-5564(86)90161-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007204118"
        ], 
        "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/bf02458863", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027538383", 
          "https://doi.org/10.1007/bf02458863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02458863", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027538383", 
          "https://doi.org/10.1007/bf02458863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-5193(84)80103-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035919827"
        ], 
        "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": "https://doi.org/10.1016/0022-5193(83)90296-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051993497"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/10.2.189", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059413361"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/32.6177", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061154340"
        ], 
        "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.1017/cbo9780511574931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098674485"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.", 
    "editor": [
      {
        "familyName": "Min", 
        "givenName": "Geyong", 
        "type": "Person"
      }, 
      {
        "familyName": "Di Martino", 
        "givenName": "Beniamino", 
        "type": "Person"
      }, 
      {
        "familyName": "Yang", 
        "givenName": "Laurence T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Guo", 
        "givenName": "Minyi", 
        "type": "Person"
      }, 
      {
        "familyName": "R\u00fcnger", 
        "givenName": "Gudula", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11942634_23", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-49860-5", 
        "978-3-540-49862-9"
      ], 
      "name": "Frontiers of High Performance Computing and Networking \u2013 ISPA 2006 Workshops", 
      "type": "Book"
    }, 
    "name": "An Efficient Parallel Algorithm for Ultrametric Tree Construction Based on 3PR", 
    "pagination": "215-220", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025066797"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11942634_23"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "776b206335bb14b6591a1b74a1d84a656a1dcdcd52a5021a116776ed702fccea"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11942634_23", 
      "https://app.dimensions.ai/details/publication/pub.1025066797"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000355_0000000355/records_52991_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11942634_23"
  }
]
 

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/11942634_23'

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/11942634_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11942634_23'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11942634_23'


 

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

147 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11942634_23 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N712bf328d0e74eee8e8db96817996e02
4 schema:citation sg:pub.10.1007/bf02458863
5 sg:pub.10.1023/a:1009885610075
6 https://doi.org/10.1016/0022-5193(83)90296-5
7 https://doi.org/10.1016/0025-5564(82)90027-x
8 https://doi.org/10.1016/0025-5564(86)90161-6
9 https://doi.org/10.1016/s0022-5193(84)80103-4
10 https://doi.org/10.1017/cbo9780511574931
11 https://doi.org/10.1093/bioinformatics/10.2.189
12 https://doi.org/10.1093/bioinformatics/12.4.357
13 https://doi.org/10.1109/32.6177
14 https://doi.org/10.1126/science.1840702
15 schema:datePublished 2006
16 schema:datePublishedReg 2006-01-01
17 schema:description In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.
18 schema:editor N482e05fd39ad4971a4e77e956e7b562c
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf Nc057af6ace4447ae96e361e4ec8419c1
23 schema:name An Efficient Parallel Algorithm for Ultrametric Tree Construction Based on 3PR
24 schema:pagination 215-220
25 schema:productId N15a4cf8f3bb94bf4a1368688c541b280
26 N4cc85d943d074b7d88df4b40e388852d
27 N7da7e6294da34c4cb341f9f484639f62
28 schema:publisher N550dbe7dc61b4452b73d63ad11f6d5ae
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025066797
30 https://doi.org/10.1007/11942634_23
31 schema:sdDatePublished 2019-04-16T07:26
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N1b5e7e79028d4d2fb26c13d1a62240e1
34 schema:url https://link.springer.com/10.1007%2F11942634_23
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N115480c79a52492a99249f9ee0b3a5a2 rdf:first N60e79952415845dfbff5de9083afbc86
39 rdf:rest N309aa9043c1c4cf497041d9ad7067e8f
40 N15a4cf8f3bb94bf4a1368688c541b280 schema:name doi
41 schema:value 10.1007/11942634_23
42 rdf:type schema:PropertyValue
43 N1b5e7e79028d4d2fb26c13d1a62240e1 schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N25ee32cd1eac473d8af0845e0012be07 rdf:first sg:person.0665540554.26
46 rdf:rest Nbc6a2766a17447b4a9d982aafe680ebb
47 N269678be4c294e1aa602a00a2952fa76 rdf:first sg:person.016405705547.11
48 rdf:rest N25ee32cd1eac473d8af0845e0012be07
49 N309aa9043c1c4cf497041d9ad7067e8f rdf:first N7b2cc297f660425ea342e6f936f2f2bf
50 rdf:rest N97ee5a597af74fd4a786865b3e1d89be
51 N453575665c014751926459db3a869349 schema:familyName Di Martino
52 schema:givenName Beniamino
53 rdf:type schema:Person
54 N482e05fd39ad4971a4e77e956e7b562c rdf:first N60a2c113e285498b9318b0b6c87061d4
55 rdf:rest N99618c3192b747bfa709598c9ef6044c
56 N4cc85d943d074b7d88df4b40e388852d schema:name dimensions_id
57 schema:value pub.1025066797
58 rdf:type schema:PropertyValue
59 N550dbe7dc61b4452b73d63ad11f6d5ae schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 N60a2c113e285498b9318b0b6c87061d4 schema:familyName Min
63 schema:givenName Geyong
64 rdf:type schema:Person
65 N60e79952415845dfbff5de9083afbc86 schema:familyName Yang
66 schema:givenName Laurence T.
67 rdf:type schema:Person
68 N712bf328d0e74eee8e8db96817996e02 rdf:first sg:person.015566066077.39
69 rdf:rest N269678be4c294e1aa602a00a2952fa76
70 N7b2cc297f660425ea342e6f936f2f2bf schema:familyName Guo
71 schema:givenName Minyi
72 rdf:type schema:Person
73 N7da7e6294da34c4cb341f9f484639f62 schema:name readcube_id
74 schema:value 776b206335bb14b6591a1b74a1d84a656a1dcdcd52a5021a116776ed702fccea
75 rdf:type schema:PropertyValue
76 N8487615b9d2e4e47859eaef939b94f28 schema:familyName Rünger
77 schema:givenName Gudula
78 rdf:type schema:Person
79 N8eb54433ba254eb398bc3c0370221e89 schema:name Institute of Molecular and Cellular Biology, National Tsing Hua University
80 rdf:type schema:Organization
81 N97ee5a597af74fd4a786865b3e1d89be rdf:first N8487615b9d2e4e47859eaef939b94f28
82 rdf:rest rdf:nil
83 N99618c3192b747bfa709598c9ef6044c rdf:first N453575665c014751926459db3a869349
84 rdf:rest N115480c79a52492a99249f9ee0b3a5a2
85 Nbc6a2766a17447b4a9d982aafe680ebb rdf:first sg:person.01312526135.27
86 rdf:rest rdf:nil
87 Nc057af6ace4447ae96e361e4ec8419c1 schema:isbn 978-3-540-49860-5
88 978-3-540-49862-9
89 schema:name Frontiers of High Performance Computing and Networking – ISPA 2006 Workshops
90 rdf:type schema:Book
91 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
92 schema:name Mathematical Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
95 schema:name Applied Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
98 schema:familyName Tang
99 schema:givenName Chuan Yi
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
101 rdf:type schema:Person
102 sg:person.015566066077.39 schema:affiliation https://www.grid.ac/institutes/grid.411655.2
103 schema:familyName Yu
104 schema:givenName Kun-Ming
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015566066077.39
106 rdf:type schema:Person
107 sg:person.016405705547.11 schema:affiliation https://www.grid.ac/institutes/grid.411655.2
108 schema:familyName Zhou
109 schema:givenName Jiayi
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016405705547.11
111 rdf:type schema:Person
112 sg:person.0665540554.26 schema:affiliation N8eb54433ba254eb398bc3c0370221e89
113 schema:familyName Lin
114 schema:givenName Chun-Yuan
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0665540554.26
116 rdf:type schema:Person
117 sg:pub.10.1007/bf02458863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027538383
118 https://doi.org/10.1007/bf02458863
119 rdf:type schema:CreativeWork
120 sg:pub.10.1023/a:1009885610075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044701682
121 https://doi.org/10.1023/a:1009885610075
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/0022-5193(83)90296-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051993497
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/0025-5564(82)90027-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013420601
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/0025-5564(86)90161-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007204118
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/s0022-5193(84)80103-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035919827
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1017/cbo9780511574931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098674485
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1093/bioinformatics/10.2.189 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059413361
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1093/bioinformatics/12.4.357 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000618136
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1109/32.6177 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061154340
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1126/science.1840702 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062509890
140 rdf:type schema:CreativeWork
141 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
142 schema:name Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C
143 rdf:type schema:Organization
144 https://www.grid.ac/institutes/grid.411655.2 schema:alternateName Chung Hua University
145 schema:name Department of of Computer Science and Information Engineering, Chung Hua University
146 Institute of Engineering Science, Chung Hua University
147 rdf:type schema:Organization
 




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


...