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


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-06-04

AUTHORS

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

ABSTRACT

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 inequalities, 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 developed an efficient branch and bound algorithm for constructing the minimum ultrametric tree for both metric and nonmetric 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

299-308

References to SciGraph publications

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-64824-6
978-3-540-68535-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-68535-9_34

DOI

http://dx.doi.org/10.1007/3-540-68535-9_34

DIMENSIONS

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


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": [
            "Dept. 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": [
            "Dept. 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": [
            "Dept. 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": "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"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511574931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098674485"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-06-04", 
    "datePublishedReg": "2002-06-04", 
    "description": "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 inequalities, 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 developed an efficient branch and bound algorithm for constructing the minimum ultrametric tree for both metric and nonmetric 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.", 
    "editor": [
      {
        "familyName": "Hsu", 
        "givenName": "Wen-Lian", 
        "type": "Person"
      }, 
      {
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-68535-9_34", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64824-6", 
        "978-3-540-68535-7"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices", 
    "pagination": "299-308", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-68535-9_34"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "862d23092a0c26658a3f1ca6ad5bbab114d010e46cf9f1a4072c1e20ce988915"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028165771"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-68535-9_34", 
      "https://app.dimensions.ai/details/publication/pub.1028165771"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:30", 
    "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_99806_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-68535-9_34"
  }
]
 

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-68535-9_34'

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-68535-9_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-68535-9_34'

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-68535-9_34'


 

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

126 TRIPLES      23 PREDICATES      38 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-68535-9_34 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfef15b4bda604e728598594cafa5b497
4 schema:citation sg:pub.10.1007/bf01188585
5 sg:pub.10.1007/bf01733209
6 sg:pub.10.1007/bf02458863
7 https://doi.org/10.1016/0020-0190(88)90090-7
8 https://doi.org/10.1016/0022-5193(83)90296-5
9 https://doi.org/10.1016/0025-5564(82)90027-x
10 https://doi.org/10.1016/0025-5564(86)90161-6
11 https://doi.org/10.1016/s0022-5193(84)80103-4
12 https://doi.org/10.1016/s0196-8858(82)80004-3
13 https://doi.org/10.1017/cbo9780511574931
14 https://doi.org/10.1137/0403001
15 https://doi.org/10.1137/0406041
16 schema:datePublished 2002-06-04
17 schema:datePublishedReg 2002-06-04
18 schema:description 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 inequalities, 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 developed an efficient branch and bound algorithm for constructing the minimum ultrametric tree for both metric and nonmetric 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:editor N093f33eb3ce3415db4a4ca578839db2a
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N5464749fcbb842c9b31cbcf81a0e052a
24 schema:name Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices
25 schema:pagination 299-308
26 schema:productId N2f334dc88b2941129920b5ae534327ab
27 N9686d63166734599b2b01ef294b4be3a
28 Nd55ffd5957524c6bb2262a21286f0b88
29 schema:publisher N441c5908c5724a8f916ac553e1fcb486
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028165771
31 https://doi.org/10.1007/3-540-68535-9_34
32 schema:sdDatePublished 2019-04-16T05:30
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Ne58622040043468c95bbc6bfdc097385
35 schema:url https://link.springer.com/10.1007%2F3-540-68535-9_34
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N093f33eb3ce3415db4a4ca578839db2a rdf:first N95a878fa4f6e40858cc48b9a7c00fd97
40 rdf:rest N2743fa0349304fa593a706374f717256
41 N198edca7f85b4d6997944d48d707701a schema:familyName Kao
42 schema:givenName Ming-Yang
43 rdf:type schema:Person
44 N2743fa0349304fa593a706374f717256 rdf:first N198edca7f85b4d6997944d48d707701a
45 rdf:rest rdf:nil
46 N2f334dc88b2941129920b5ae534327ab schema:name doi
47 schema:value 10.1007/3-540-68535-9_34
48 rdf:type schema:PropertyValue
49 N441c5908c5724a8f916ac553e1fcb486 schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 N5464749fcbb842c9b31cbcf81a0e052a schema:isbn 978-3-540-64824-6
53 978-3-540-68535-7
54 schema:name Computing and Combinatorics
55 rdf:type schema:Book
56 N95a878fa4f6e40858cc48b9a7c00fd97 schema:familyName Hsu
57 schema:givenName Wen-Lian
58 rdf:type schema:Person
59 N9686d63166734599b2b01ef294b4be3a schema:name dimensions_id
60 schema:value pub.1028165771
61 rdf:type schema:PropertyValue
62 N98a2d6298ca44b4aad9eff8ec37331e7 rdf:first sg:person.01063515113.26
63 rdf:rest Nbdb0b47becea46c4b57143ca7e5efe96
64 Nbdb0b47becea46c4b57143ca7e5efe96 rdf:first sg:person.01312526135.27
65 rdf:rest rdf:nil
66 Nd55ffd5957524c6bb2262a21286f0b88 schema:name readcube_id
67 schema:value 862d23092a0c26658a3f1ca6ad5bbab114d010e46cf9f1a4072c1e20ce988915
68 rdf:type schema:PropertyValue
69 Ne58622040043468c95bbc6bfdc097385 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 Nfef15b4bda604e728598594cafa5b497 rdf:first sg:person.013045767237.23
72 rdf:rest N98a2d6298ca44b4aad9eff8ec37331e7
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
77 schema:name Computation Theory and Mathematics
78 rdf:type schema:DefinedTerm
79 sg:person.01063515113.26 schema:affiliation https://www.grid.ac/institutes/grid.412550.7
80 schema:familyName Chao
81 schema:givenName Kun-Mao
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26
83 rdf:type schema:Person
84 sg:person.013045767237.23 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
85 schema:familyName Wu
86 schema:givenName Bang Ye
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
88 rdf:type schema:Person
89 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
90 schema:familyName Tang
91 schema:givenName Chuan Yi
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
93 rdf:type schema:Person
94 sg:pub.10.1007/bf01188585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004227195
95 https://doi.org/10.1007/bf01188585
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/bf01733209 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014931197
98 https://doi.org/10.1007/bf01733209
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf02458863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027538383
101 https://doi.org/10.1007/bf02458863
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0020-0190(88)90090-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012715551
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/0022-5193(83)90296-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051993497
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/0025-5564(82)90027-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013420601
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0025-5564(86)90161-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007204118
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/s0022-5193(84)80103-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035919827
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/s0196-8858(82)80004-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032724280
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1017/cbo9780511574931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098674485
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1137/0403001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844592
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1137/0406041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844846
120 rdf:type schema:CreativeWork
121 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
122 schema:name Dept. of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.412550.7 schema:alternateName Providence University
125 schema:name Dept. of Computer Science and Information Management, Providence University, Shalu, Taiwan, R.O.C.
126 rdf:type schema:Organization
 




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


...