A New 2-Approximation Algorithm for rSPR Distance View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-05-31

AUTHORS

Zhi-Zhong Chen , Youta Harada , Lusheng Wang

ABSTRACT

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2 in polynomial time and its analysis is based on the duality theory of linear programming. In this paper, we present a cubic-time approximation algorithm for rSPR distance that achieves a ratio of 2. Our algorithm is based on the notion of key and several structural lemmas; its analysis is purely combinatorial and explicitly uses a search tree for computing rSPR distance exactly. Our experimental results show that the algorithm can be implemented into a program which outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best. More... »

PAGES

128-139

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-59575-7_12

DOI

http://dx.doi.org/10.1007/978-3-319-59575-7_12

DIMENSIONS

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


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": "Division of Information System Design, Tokyo Denki University, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, Tokyo, 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": "Division of Information System Design, Tokyo Denki University, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harada", 
        "givenName": "Youta", 
        "id": "sg:person.011526465541.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Kowloon Tong, HK, China", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Kowloon Tong, HK, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-05-31", 
    "datePublishedReg": "2017-05-31", 
    "description": "Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2 in polynomial time and its analysis is based on the duality theory of linear programming. In this paper, we present a cubic-time approximation algorithm for rSPR distance that achieves a ratio of 2. Our algorithm is based on the notion of key and several structural lemmas; its analysis is purely combinatorial and explicitly uses a search tree for computing rSPR distance exactly. Our experimental results show that the algorithm can be implemented into a program which outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best.", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Zhipeng", 
        "type": "Person"
      }, 
      {
        "familyName": "Daescu", 
        "givenName": "Ovidiu", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Min", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-59575-7_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-59574-0", 
        "978-3-319-59575-7"
      ], 
      "name": "Bioinformatics Research and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "set of species", 
      "rSPR distance", 
      "different phylogenetic trees", 
      "phylogenetic tree", 
      "hybridization events", 
      "different genes", 
      "regraft distance", 
      "subtree prune", 
      "species", 
      "trees", 
      "approximation algorithm", 
      "genes", 
      "best approximation algorithm", 
      "search tree", 
      "polynomial time", 
      "algorithm", 
      "linear programming", 
      "experimental results", 
      "structural lemma", 
      "evolution", 
      "dissimilarity", 
      "analysis", 
      "upper bounds", 
      "set", 
      "distance", 
      "programming", 
      "events", 
      "prunes", 
      "duality theory", 
      "NPs", 
      "applications", 
      "bounds", 
      "results", 
      "output", 
      "ratio", 
      "notion", 
      "lemma", 
      "program", 
      "time", 
      "purpose", 
      "theory", 
      "problem", 
      "cases", 
      "paper"
    ], 
    "name": "A New 2-Approximation Algorithm for rSPR Distance", 
    "pagination": "128-139", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1085724469"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-59575-7_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-59575-7_12", 
      "https://app.dimensions.ai/details/publication/pub.1085724469"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_31.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-59575-7_12"
  }
]
 

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/978-3-319-59575-7_12'

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/978-3-319-59575-7_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-59575-7_12'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-59575-7_12'


 

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

131 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-59575-7_12 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N63b2adc40b0e4f478895bd8befda4559
4 schema:datePublished 2017-05-31
5 schema:datePublishedReg 2017-05-31
6 schema:description Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2 in polynomial time and its analysis is based on the duality theory of linear programming. In this paper, we present a cubic-time approximation algorithm for rSPR distance that achieves a ratio of 2. Our algorithm is based on the notion of key and several structural lemmas; its analysis is purely combinatorial and explicitly uses a search tree for computing rSPR distance exactly. Our experimental results show that the algorithm can be implemented into a program which outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best.
7 schema:editor Nd1fdb9b1b6664d55a5d52926669c8c3a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8fe7425b6b794b0797bb35b55499eac8
12 schema:keywords NPs
13 algorithm
14 analysis
15 applications
16 approximation algorithm
17 best approximation algorithm
18 bounds
19 cases
20 different genes
21 different phylogenetic trees
22 dissimilarity
23 distance
24 duality theory
25 events
26 evolution
27 experimental results
28 genes
29 hybridization events
30 lemma
31 linear programming
32 notion
33 output
34 paper
35 phylogenetic tree
36 polynomial time
37 problem
38 program
39 programming
40 prunes
41 purpose
42 rSPR distance
43 ratio
44 regraft distance
45 results
46 search tree
47 set
48 set of species
49 species
50 structural lemma
51 subtree prune
52 theory
53 time
54 trees
55 upper bounds
56 schema:name A New 2-Approximation Algorithm for rSPR Distance
57 schema:pagination 128-139
58 schema:productId N2e892877c1ec4c99951efaed7fa64c08
59 N88b460d8aa444ae5b2cc96b3211e6efd
60 schema:publisher N795c613fbf994eba9b5e14f4d30c4a6a
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085724469
62 https://doi.org/10.1007/978-3-319-59575-7_12
63 schema:sdDatePublished 2022-05-10T10:46
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Ndfdbb5683e7b436ca9404ec89c5251d4
66 schema:url https://doi.org/10.1007/978-3-319-59575-7_12
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N2e892877c1ec4c99951efaed7fa64c08 schema:name dimensions_id
71 schema:value pub.1085724469
72 rdf:type schema:PropertyValue
73 N359c946f2b5d4d319bc48e333f39c3b8 rdf:first sg:person.01105113721.52
74 rdf:rest rdf:nil
75 N5e21050aa4e041939fe9bef66bc99690 rdf:first N706dedf7d73f4e769e10cea81da789bb
76 rdf:rest Ne37bc7b615934138b3e7a1b446f6f60b
77 N63b2adc40b0e4f478895bd8befda4559 rdf:first sg:person.015654265661.98
78 rdf:rest N7099b914402b4a33a2c5bcb7f086e682
79 N706dedf7d73f4e769e10cea81da789bb schema:familyName Daescu
80 schema:givenName Ovidiu
81 rdf:type schema:Person
82 N7099b914402b4a33a2c5bcb7f086e682 rdf:first sg:person.011526465541.54
83 rdf:rest N359c946f2b5d4d319bc48e333f39c3b8
84 N795c613fbf994eba9b5e14f4d30c4a6a schema:name Springer Nature
85 rdf:type schema:Organisation
86 N88b460d8aa444ae5b2cc96b3211e6efd schema:name doi
87 schema:value 10.1007/978-3-319-59575-7_12
88 rdf:type schema:PropertyValue
89 N8fe7425b6b794b0797bb35b55499eac8 schema:isbn 978-3-319-59574-0
90 978-3-319-59575-7
91 schema:name Bioinformatics Research and Applications
92 rdf:type schema:Book
93 Nd1fdb9b1b6664d55a5d52926669c8c3a rdf:first Nd92c1524523d40e4b51810a84322bb69
94 rdf:rest N5e21050aa4e041939fe9bef66bc99690
95 Nd92c1524523d40e4b51810a84322bb69 schema:familyName Cai
96 schema:givenName Zhipeng
97 rdf:type schema:Person
98 Nde5759a29d384f2e86d1d15d4a0a9173 schema:familyName Li
99 schema:givenName Min
100 rdf:type schema:Person
101 Ndfdbb5683e7b436ca9404ec89c5251d4 schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 Ne37bc7b615934138b3e7a1b446f6f60b rdf:first Nde5759a29d384f2e86d1d15d4a0a9173
104 rdf:rest rdf:nil
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
109 schema:name Computation Theory and Mathematics
110 rdf:type schema:DefinedTerm
111 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
112 schema:familyName Wang
113 schema:givenName Lusheng
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
115 rdf:type schema:Person
116 sg:person.011526465541.54 schema:affiliation grid-institutes:grid.412773.4
117 schema:familyName Harada
118 schema:givenName Youta
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54
120 rdf:type schema:Person
121 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
122 schema:familyName Chen
123 schema:givenName Zhi-Zhong
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
125 rdf:type schema:Person
126 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Kowloon Tong, HK, China
127 schema:name Department of Computer Science, City University of Hong Kong, Kowloon Tong, HK, China
128 rdf:type schema:Organization
129 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Tokyo, Japan
130 schema:name Division of Information System Design, Tokyo Denki University, Tokyo, Japan
131 rdf:type schema:Organization
 




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


...