Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-07

AUTHORS

Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang

ABSTRACT

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that dT(i, j) ≥ M[i, j] for all i, j and is minimum, where dT(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + ⌈log n⌉), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species. More... »

PAGES

199-211

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1009885610075

DOI

http://dx.doi.org/10.1023/a:1009885610075

DIMENSIONS

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


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": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Providence University", 
          "id": "https://www.grid.ac/institutes/grid.412550.7", 
          "name": [
            "Department of Computer Science and Information Management, Providence University, Shalu, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chao", 
        "givenName": "Kun-Mao", 
        "id": "sg:person.01063515113.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.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, 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": "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/0025-5564(86)90161-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007204118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007977430", 
          "https://doi.org/10.1007/978-1-4684-2001-2_9"
        ], 
        "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/bf01733209", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014931197", 
          "https://doi.org/10.1007/bf01733209"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01733209", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014931197", 
          "https://doi.org/10.1007/bf01733209"
        ], 
        "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/s0196-8858(82)80004-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032724280"
        ], 
        "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": "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.1137/0403001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844592"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0406041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844846"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999-07", 
    "datePublishedReg": "1999-07-01", 
    "description": "An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that dT(i, j) \u2265 M[i, j] for all i, j and is minimum, where dT(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + \u2308log n\u2309), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1009885610075", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "3"
      }
    ], 
    "name": "Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices", 
    "pagination": "199-211", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d4ee8948da83c63cf2c001cc9b849cacf5d4ab2cefa610540fa950ffba88cefb"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1009885610075"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044701682"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1009885610075", 
      "https://app.dimensions.ai/details/publication/pub.1044701682"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T01:57", 
    "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_8700_00000501.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023/A:1009885610075"
  }
]
 

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.1023/a:1009885610075'

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.1023/a:1009885610075'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1009885610075'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1009885610075'


 

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

118 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1009885610075 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nca2f2923c44845fd8e2f3b4004f192c6
4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
5 sg:pub.10.1007/bf01188585
6 sg:pub.10.1007/bf01733209
7 sg:pub.10.1007/bf02458863
8 https://doi.org/10.1016/0020-0190(88)90090-7
9 https://doi.org/10.1016/0022-5193(83)90296-5
10 https://doi.org/10.1016/0025-5564(82)90027-x
11 https://doi.org/10.1016/0025-5564(86)90161-6
12 https://doi.org/10.1016/s0022-5193(84)80103-4
13 https://doi.org/10.1016/s0196-8858(82)80004-3
14 https://doi.org/10.1137/0403001
15 https://doi.org/10.1137/0406041
16 schema:datePublished 1999-07
17 schema:datePublishedReg 1999-07-01
18 schema:description An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that dT(i, j) ≥ M[i, j] for all i, j and is minimum, where dT(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + ⌈log n⌉), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N7074ba75dfb143d2892737d6496290d3
23 Nc12c2be248d944bd913b3132e2dfac12
24 sg:journal.1036683
25 schema:name Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices
26 schema:pagination 199-211
27 schema:productId N1f175dd77bb947f8ae1991211926e0b3
28 N2742eed4300c4435afc80bc127ea9173
29 N6c3b1d6ddef0453fbc05c4a794b82b02
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044701682
31 https://doi.org/10.1023/a:1009885610075
32 schema:sdDatePublished 2019-04-11T01:57
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N2f80fa42a27e432a84dbb83d8f49aa40
35 schema:url http://link.springer.com/10.1023/A:1009885610075
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N1f175dd77bb947f8ae1991211926e0b3 schema:name doi
40 schema:value 10.1023/a:1009885610075
41 rdf:type schema:PropertyValue
42 N2742eed4300c4435afc80bc127ea9173 schema:name dimensions_id
43 schema:value pub.1044701682
44 rdf:type schema:PropertyValue
45 N2df19bd66cc6406881aa9dd8ab6832e0 rdf:first sg:person.01312526135.27
46 rdf:rest rdf:nil
47 N2f80fa42a27e432a84dbb83d8f49aa40 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N6c3b1d6ddef0453fbc05c4a794b82b02 schema:name readcube_id
50 schema:value d4ee8948da83c63cf2c001cc9b849cacf5d4ab2cefa610540fa950ffba88cefb
51 rdf:type schema:PropertyValue
52 N7074ba75dfb143d2892737d6496290d3 schema:issueNumber 2-3
53 rdf:type schema:PublicationIssue
54 N9dbca861bdb046b6bc526659a18b7b38 rdf:first sg:person.01063515113.26
55 rdf:rest N2df19bd66cc6406881aa9dd8ab6832e0
56 Nc12c2be248d944bd913b3132e2dfac12 schema:volumeNumber 3
57 rdf:type schema:PublicationVolume
58 Nca2f2923c44845fd8e2f3b4004f192c6 rdf:first sg:person.013045767237.23
59 rdf:rest N9dbca861bdb046b6bc526659a18b7b38
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computation Theory and Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1036683 schema:issn 1382-6905
67 1573-2886
68 schema:name Journal of Combinatorial Optimization
69 rdf:type schema:Periodical
70 sg:person.01063515113.26 schema:affiliation https://www.grid.ac/institutes/grid.412550.7
71 schema:familyName Chao
72 schema:givenName Kun-Mao
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26
74 rdf:type schema:Person
75 sg:person.013045767237.23 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
76 schema:familyName Wu
77 schema:givenName Bang Ye
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
79 rdf:type schema:Person
80 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
81 schema:familyName Tang
82 schema:givenName Chuan Yi
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
84 rdf:type schema:Person
85 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
86 https://doi.org/10.1007/978-1-4684-2001-2_9
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf01188585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004227195
89 https://doi.org/10.1007/bf01188585
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/bf01733209 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014931197
92 https://doi.org/10.1007/bf01733209
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/bf02458863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027538383
95 https://doi.org/10.1007/bf02458863
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/0020-0190(88)90090-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012715551
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0022-5193(83)90296-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051993497
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0025-5564(82)90027-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013420601
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0025-5564(86)90161-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007204118
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/s0022-5193(84)80103-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035919827
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/s0196-8858(82)80004-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032724280
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/0403001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844592
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0406041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844846
112 rdf:type schema:CreativeWork
113 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
114 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C
115 rdf:type schema:Organization
116 https://www.grid.ac/institutes/grid.412550.7 schema:alternateName Providence University
117 schema:name Department of Computer Science and Information Management, Providence University, Shalu, Taiwan, R.O.C
118 rdf:type schema:Organization
 




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


...