Computing Phylogenetic Roots with Bounded Degrees and Errors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-08-02

AUTHORS

Zhi-Zhong Chen , Tao Jiang , Guo-Hui Lin

ABSTRACT

Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E) where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) ∈ E if and only if dt(u,v) ≤ k for some fixed threshold k, where dt(u,v) denotes the distance between u and v in tree T. This is called the Phylogenetic KTH Root Problem (PRk), and such a tree T, if exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k ≤ 4. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a linear-time algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, as in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is only required to be an approximate root of the input graph. We show that this and other related problems are computationally intractable. More... »

PAGES

377-388

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44634-6_35

DOI

http://dx.doi.org/10.1007/3-540-44634-6_35

DIMENSIONS

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


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": "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Department of Computer Science, University of California, 92521, Riverside, CA", 
            "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.015107424575.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada", 
            "Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Guo-Hui", 
        "id": "sg:person.01130357621.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-08-02", 
    "datePublishedReg": "2001-08-02", 
    "description": "Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E) where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) \u2208 E if and only if dt(u,v) \u2264 k for some fixed threshold k, where dt(u,v) denotes the distance between u and v in tree T. This is called the Phylogenetic KTH Root Problem (PRk), and such a tree T, if exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k \u2264 4. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a linear-time algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, as in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is only required to be an approximate root of the input graph. We show that this and other related problems are computationally intractable.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44634-6_35", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42423-9", 
        "978-3-540-44634-7"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "kth roots", 
      "graph G", 
      "linear time algorithm", 
      "phylogenetic roots", 
      "high similarity", 
      "approximate roots", 
      "generalized version", 
      "computational complexity", 
      "set of species", 
      "input graph", 
      "graph G.", 
      "natural restrictions", 
      "phylogeny reconstruction problem", 
      "reconstruction problem", 
      "tree T", 
      "evolutionary biology", 
      "T. This", 
      "maximum degree", 
      "related problems", 
      "phylogeny", 
      "similarity data", 
      "threshold k", 
      "vertices", 
      "important problem", 
      "species", 
      "problem", 
      "main contribution", 
      "internal nodes", 
      "roots", 
      "error", 
      "external nodes", 
      "root problem", 
      "graph", 
      "algorithm", 
      "biology", 
      "similarity", 
      "PRK", 
      "nodes", 
      "complexity", 
      "set", 
      "G.", 
      "version", 
      "constants", 
      "distance", 
      "data", 
      "restriction", 
      "degree", 
      "exists", 
      "elements", 
      "contribution", 
      "THI", 
      "hand", 
      "practice", 
      "paper"
    ], 
    "name": "Computing Phylogenetic Roots with Bounded Degrees and Errors", 
    "pagination": "377-388", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017037094"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44634-6_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44634-6_35", 
      "https://app.dimensions.ai/details/publication/pub.1017037094"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_384.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44634-6_35"
  }
]
 

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-44634-6_35'

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-44634-6_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44634-6_35'

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-44634-6_35'


 

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

146 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44634-6_35 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N29d2328cee7d4ecfb982503ae486c1bf
4 schema:datePublished 2001-08-02
5 schema:datePublishedReg 2001-08-02
6 schema:description Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E) where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) ∈ E if and only if dt(u,v) ≤ k for some fixed threshold k, where dt(u,v) denotes the distance between u and v in tree T. This is called the Phylogenetic KTH Root Problem (PRk), and such a tree T, if exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k ≤ 4. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a linear-time algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, as in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is only required to be an approximate root of the input graph. We show that this and other related problems are computationally intractable.
7 schema:editor N68567f1f28b9446a871be38ceaab16a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb6a3590849474afaa7e25bfef6328b94
12 schema:keywords G.
13 PRK
14 T. This
15 THI
16 algorithm
17 approximate roots
18 biology
19 complexity
20 computational complexity
21 constants
22 contribution
23 data
24 degree
25 distance
26 elements
27 error
28 evolutionary biology
29 exists
30 external nodes
31 generalized version
32 graph
33 graph G
34 graph G.
35 hand
36 high similarity
37 important problem
38 input graph
39 internal nodes
40 kth roots
41 linear time algorithm
42 main contribution
43 maximum degree
44 natural restrictions
45 nodes
46 paper
47 phylogenetic roots
48 phylogeny
49 phylogeny reconstruction problem
50 practice
51 problem
52 reconstruction problem
53 related problems
54 restriction
55 root problem
56 roots
57 set
58 set of species
59 similarity
60 similarity data
61 species
62 threshold k
63 tree T
64 version
65 vertices
66 schema:name Computing Phylogenetic Roots with Bounded Degrees and Errors
67 schema:pagination 377-388
68 schema:productId N3fdf6b068d9543ae9482e410cca9c90e
69 N77fe5ce0cbcb46c1b10893a18f4438d4
70 schema:publisher N92246aae9dd94a81a6809c4519f8bc50
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017037094
72 https://doi.org/10.1007/3-540-44634-6_35
73 schema:sdDatePublished 2022-05-20T07:47
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher N24583d4843b54dfba5992920940c8494
76 schema:url https://doi.org/10.1007/3-540-44634-6_35
77 sgo:license sg:explorer/license/
78 sgo:sdDataset chapters
79 rdf:type schema:Chapter
80 N24583d4843b54dfba5992920940c8494 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 N29d2328cee7d4ecfb982503ae486c1bf rdf:first sg:person.015654265661.98
83 rdf:rest Nadd63edb0cb845b38701288e142b5641
84 N3fdf6b068d9543ae9482e410cca9c90e schema:name doi
85 schema:value 10.1007/3-540-44634-6_35
86 rdf:type schema:PropertyValue
87 N4839f02881aa4920a6c75e1ce2bc52be schema:familyName Tamassia
88 schema:givenName Roberto
89 rdf:type schema:Person
90 N66f399d4ca4b4576aa750cb4f0f3c444 schema:familyName Dehne
91 schema:givenName Frank
92 rdf:type schema:Person
93 N68567f1f28b9446a871be38ceaab16a2 rdf:first N66f399d4ca4b4576aa750cb4f0f3c444
94 rdf:rest N863a22d21c5b47948843e6243a537b27
95 N6fadd03dd8714a3c984182909211d47e rdf:first N4839f02881aa4920a6c75e1ce2bc52be
96 rdf:rest rdf:nil
97 N77fe5ce0cbcb46c1b10893a18f4438d4 schema:name dimensions_id
98 schema:value pub.1017037094
99 rdf:type schema:PropertyValue
100 N7bcf5ed936dd4a10895780312b30a531 schema:familyName Sack
101 schema:givenName Jörg-Rüdiger
102 rdf:type schema:Person
103 N863a22d21c5b47948843e6243a537b27 rdf:first N7bcf5ed936dd4a10895780312b30a531
104 rdf:rest N6fadd03dd8714a3c984182909211d47e
105 N92246aae9dd94a81a6809c4519f8bc50 schema:name Springer Nature
106 rdf:type schema:Organisation
107 Na45043306985434aa7668b4fbcfca10b rdf:first sg:person.01130357621.02
108 rdf:rest rdf:nil
109 Nadd63edb0cb845b38701288e142b5641 rdf:first sg:person.015107424575.17
110 rdf:rest Na45043306985434aa7668b4fbcfca10b
111 Nb6a3590849474afaa7e25bfef6328b94 schema:isbn 978-3-540-42423-9
112 978-3-540-44634-7
113 schema:name Algorithms and Data Structures
114 rdf:type schema:Book
115 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
116 schema:name Information and Computing Sciences
117 rdf:type schema:DefinedTerm
118 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
119 schema:name Computation Theory and Mathematics
120 rdf:type schema:DefinedTerm
121 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.46078.3d
122 schema:familyName Lin
123 schema:givenName Guo-Hui
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
125 rdf:type schema:Person
126 sg:person.015107424575.17 schema:affiliation grid-institutes:grid.25073.33
127 schema:familyName Jiang
128 schema:givenName Tao
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17
130 rdf:type schema:Person
131 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
132 schema:familyName Chen
133 schema:givenName Zhi-Zhong
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
135 rdf:type schema:Person
136 grid-institutes:grid.25073.33 schema:alternateName Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
137 schema:name Department of Computer Science, University of California, 92521, Riverside, CA
138 Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
139 rdf:type schema:Organization
140 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
141 schema:name Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
142 rdf:type schema:Organization
143 grid-institutes:grid.46078.3d schema:alternateName Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
144 schema:name Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
145 Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
146 rdf:type schema:Organization
 




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


...