Ultrametric networks: a new tool for phylogenetic analysis View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-03-05

AUTHORS

Alberto Apostolico, Matteo Comin, Andres Dress, Laxmi Parida

ABSTRACT

BackgroundThe large majority of optimization problems related to the inference of distance‐based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.ResultsThis paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availabilityhttp://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html More... »

PAGES

7

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1186/1748-7188-8-7

DOI

http://dx.doi.org/10.1186/1748-7188-8-7

DIMENSIONS

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

PUBMED

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, 30332, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, 30332, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Apostolico", 
        "givenName": "Alberto", 
        "id": "sg:person.010463461106.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010463461106.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Information Engineering, University of Padova, Via Gradenigo 6/A, 35131, Padova, Italy", 
          "id": "http://www.grid.ac/institutes/grid.5608.b", 
          "name": [
            "Department of Information Engineering, University of Padova, Via Gradenigo 6/A, 35131, Padova, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Comin", 
        "givenName": "Matteo", 
        "id": "sg:person.01212037466.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212037466.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CAS\u2010MPG Partner Institute and Key Lab for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, and infinity, Bielefeld, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "CAS\u2010MPG Partner Institute and Key Lab for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, and infinity, Bielefeld, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dress", 
        "givenName": "Andres", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T. J. Watson Research Center, 10598, Yorktown Heights, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T. J. Watson Research Center, 10598, Yorktown Heights, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Parida", 
        "givenName": "Laxmi", 
        "id": "sg:person.01336557015.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01336557015.68"
        ], 
        "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/bf01890124", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021210548", 
          "https://doi.org/10.1007/bf01890124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00026-007-0302-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007345884", 
          "https://doi.org/10.1007/s00026-007-0302-5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013-03-05", 
    "datePublishedReg": "2013-03-05", 
    "description": "BackgroundThe large majority of optimization problems related to the inference of distance\u2010based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L\u221e distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.ResultsThis paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availabilityhttp://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html", 
    "genre": "article", 
    "id": "sg:pub.10.1186/1748-7188-8-7", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1036449", 
        "issn": [
          "1748-7188"
        ], 
        "name": "Algorithms for Molecular Biology", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "8"
      }
    ], 
    "keywords": [
      "molecular clock", 
      "phylogenetic analysis", 
      "ultrametric tree", 
      "distance-based trees", 
      "model of evolution", 
      "evolutionary change", 
      "distance matrix", 
      "minimum spanning tree", 
      "spanning tree", 
      "optimization problem", 
      "ultrametric distance matrix", 
      "good approximation", 
      "weighted graph", 
      "phylogeny", 
      "n vertices", 
      "ultrametric distance", 
      "polynomial time", 
      "leaves", 
      "weighted tree", 
      "simple algorithm", 
      "trees", 
      "approximation", 
      "graph", 
      "relaxed network", 
      "vertices", 
      "additive tree", 
      "artificial points", 
      "direct adaptation", 
      "transitive closure", 
      "clock", 
      "credible representation", 
      "UltraNet", 
      "new tool", 
      "algorithm", 
      "dendrogram", 
      "matrix", 
      "maximum distance", 
      "problem", 
      "network", 
      "roots", 
      "Warshall", 
      "edge", 
      "inference", 
      "adaptation", 
      "sum", 
      "distance", 
      "optimal time", 
      "solution", 
      "evolution", 
      "large majority", 
      "representation", 
      "applicability", 
      "model", 
      "analysis", 
      "purpose of classification", 
      "point", 
      "pairs", 
      "exception", 
      "postulates", 
      "same time", 
      "time", 
      "construction", 
      "respect", 
      "changes", 
      "potential", 
      "factors", 
      "fashion", 
      "good potential", 
      "majority", 
      "collection", 
      "introduction", 
      "tool", 
      "experiments", 
      "classification", 
      "weight", 
      "closure", 
      "paradigm", 
      "realm", 
      "purpose", 
      "perspective", 
      "paper"
    ], 
    "name": "Ultrametric networks: a new tool for phylogenetic analysis", 
    "pagination": "7", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000817985"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1186/1748-7188-8-7"
        ]
      }, 
      {
        "name": "pubmed_id", 
        "type": "PropertyValue", 
        "value": [
          "23497437"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1186/1748-7188-8-7", 
      "https://app.dimensions.ai/details/publication/pub.1000817985"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_586.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1186/1748-7188-8-7"
  }
]
 

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.1186/1748-7188-8-7'

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.1186/1748-7188-8-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/1748-7188-8-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/1748-7188-8-7'


 

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

182 TRIPLES      21 PREDICATES      109 URIs      98 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1186/1748-7188-8-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N70ef47d7718f4f628d8a95bfee8b125b
4 schema:citation sg:pub.10.1007/bf01188585
5 sg:pub.10.1007/bf01890124
6 sg:pub.10.1007/s00026-007-0302-5
7 schema:datePublished 2013-03-05
8 schema:datePublishedReg 2013-03-05
9 schema:description BackgroundThe large majority of optimization problems related to the inference of distance‐based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.ResultsThis paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availabilityhttp://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html
10 schema:genre article
11 schema:isAccessibleForFree true
12 schema:isPartOf N027446d87d4845ceb0e72e893daea8da
13 N5fef9c25ae7c40bd99eb3f6277b2d4b9
14 sg:journal.1036449
15 schema:keywords UltraNet
16 Warshall
17 adaptation
18 additive tree
19 algorithm
20 analysis
21 applicability
22 approximation
23 artificial points
24 changes
25 classification
26 clock
27 closure
28 collection
29 construction
30 credible representation
31 dendrogram
32 direct adaptation
33 distance
34 distance matrix
35 distance-based trees
36 edge
37 evolution
38 evolutionary change
39 exception
40 experiments
41 factors
42 fashion
43 good approximation
44 good potential
45 graph
46 inference
47 introduction
48 large majority
49 leaves
50 majority
51 matrix
52 maximum distance
53 minimum spanning tree
54 model
55 model of evolution
56 molecular clock
57 n vertices
58 network
59 new tool
60 optimal time
61 optimization problem
62 pairs
63 paper
64 paradigm
65 perspective
66 phylogenetic analysis
67 phylogeny
68 point
69 polynomial time
70 postulates
71 potential
72 problem
73 purpose
74 purpose of classification
75 realm
76 relaxed network
77 representation
78 respect
79 roots
80 same time
81 simple algorithm
82 solution
83 spanning tree
84 sum
85 time
86 tool
87 transitive closure
88 trees
89 ultrametric distance
90 ultrametric distance matrix
91 ultrametric tree
92 vertices
93 weight
94 weighted graph
95 weighted tree
96 schema:name Ultrametric networks: a new tool for phylogenetic analysis
97 schema:pagination 7
98 schema:productId N10c857d4266645c7ab2a28ef39a19da7
99 N63fed2d8ee4e424cad46d7c98a6b0294
100 N694fc26b19ce4f538ba38b2250c82936
101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000817985
102 https://doi.org/10.1186/1748-7188-8-7
103 schema:sdDatePublished 2022-09-02T15:56
104 schema:sdLicense https://scigraph.springernature.com/explorer/license/
105 schema:sdPublisher Nb344d9162e57421bb9afbb77e61b2752
106 schema:url https://doi.org/10.1186/1748-7188-8-7
107 sgo:license sg:explorer/license/
108 sgo:sdDataset articles
109 rdf:type schema:ScholarlyArticle
110 N027446d87d4845ceb0e72e893daea8da schema:issueNumber 1
111 rdf:type schema:PublicationIssue
112 N10c857d4266645c7ab2a28ef39a19da7 schema:name doi
113 schema:value 10.1186/1748-7188-8-7
114 rdf:type schema:PropertyValue
115 N2af50e9f16264ef78b79a673fd5a1b4f rdf:first Nd6dad68e726a452188ab769ac611345d
116 rdf:rest Nb3baa1a35b99433aa3e113eb5daadcc0
117 N5fef9c25ae7c40bd99eb3f6277b2d4b9 schema:volumeNumber 8
118 rdf:type schema:PublicationVolume
119 N63fed2d8ee4e424cad46d7c98a6b0294 schema:name pubmed_id
120 schema:value 23497437
121 rdf:type schema:PropertyValue
122 N694fc26b19ce4f538ba38b2250c82936 schema:name dimensions_id
123 schema:value pub.1000817985
124 rdf:type schema:PropertyValue
125 N70ef47d7718f4f628d8a95bfee8b125b rdf:first sg:person.010463461106.07
126 rdf:rest N801c2518cf5d418f8cbbefc28c21aa8d
127 N801c2518cf5d418f8cbbefc28c21aa8d rdf:first sg:person.01212037466.86
128 rdf:rest N2af50e9f16264ef78b79a673fd5a1b4f
129 Nb344d9162e57421bb9afbb77e61b2752 schema:name Springer Nature - SN SciGraph project
130 rdf:type schema:Organization
131 Nb3baa1a35b99433aa3e113eb5daadcc0 rdf:first sg:person.01336557015.68
132 rdf:rest rdf:nil
133 Nd6dad68e726a452188ab769ac611345d schema:affiliation grid-institutes:None
134 schema:familyName Dress
135 schema:givenName Andres
136 rdf:type schema:Person
137 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
138 schema:name Information and Computing Sciences
139 rdf:type schema:DefinedTerm
140 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
141 schema:name Computation Theory and Mathematics
142 rdf:type schema:DefinedTerm
143 sg:journal.1036449 schema:issn 1748-7188
144 schema:name Algorithms for Molecular Biology
145 schema:publisher Springer Nature
146 rdf:type schema:Periodical
147 sg:person.010463461106.07 schema:affiliation grid-institutes:grid.213917.f
148 schema:familyName Apostolico
149 schema:givenName Alberto
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010463461106.07
151 rdf:type schema:Person
152 sg:person.01212037466.86 schema:affiliation grid-institutes:grid.5608.b
153 schema:familyName Comin
154 schema:givenName Matteo
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212037466.86
156 rdf:type schema:Person
157 sg:person.01336557015.68 schema:affiliation grid-institutes:grid.481554.9
158 schema:familyName Parida
159 schema:givenName Laxmi
160 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01336557015.68
161 rdf:type schema:Person
162 sg:pub.10.1007/bf01188585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004227195
163 https://doi.org/10.1007/bf01188585
164 rdf:type schema:CreativeWork
165 sg:pub.10.1007/bf01890124 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021210548
166 https://doi.org/10.1007/bf01890124
167 rdf:type schema:CreativeWork
168 sg:pub.10.1007/s00026-007-0302-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007345884
169 https://doi.org/10.1007/s00026-007-0302-5
170 rdf:type schema:CreativeWork
171 grid-institutes:None schema:alternateName CAS‐MPG Partner Institute and Key Lab for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, and infinity, Bielefeld, Germany
172 schema:name CAS‐MPG Partner Institute and Key Lab for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, and infinity, Bielefeld, Germany
173 rdf:type schema:Organization
174 grid-institutes:grid.213917.f schema:alternateName College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, 30332, Atlanta, GA, USA
175 schema:name College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, 30332, Atlanta, GA, USA
176 rdf:type schema:Organization
177 grid-institutes:grid.481554.9 schema:alternateName IBM T. J. Watson Research Center, 10598, Yorktown Heights, NY, USA
178 schema:name IBM T. J. Watson Research Center, 10598, Yorktown Heights, NY, USA
179 rdf:type schema:Organization
180 grid-institutes:grid.5608.b schema:alternateName Department of Information Engineering, University of Padova, Via Gradenigo 6/A, 35131, Padova, Italy
181 schema:name Department of Information Engineering, University of Padova, Via Gradenigo 6/A, 35131, Padova, Italy
182 rdf:type schema:Organization
 




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


...