Faster Exact Computation of rSPR Distance View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Zhi-Zhong Chen , 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, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(2.415^dn\right)$\end{document} time, where n and d are the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(2.344^dn\right)$\end{document} time. Our experiments show that the new algorithm can be significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, Whidden et al.’s RSPR) for rSPR distance. More... »

PAGES

36-47

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38756-2_7

DOI

http://dx.doi.org/10.1007/978-3-642-38756-2_7

DIMENSIONS

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


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 Information System Design, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Information System Design, Tokyo Denki University, Hatoyama, 350-0394, 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 Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "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, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(2.415^dn\\right)$\\end{document} time, where n and d are the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(2.344^dn\\right)$\\end{document} time. Our experiments show that the new algorithm can be significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, Whidden et al.\u2019s RSPR) for rSPR distance.", 
    "editor": [
      {
        "familyName": "Fellows", 
        "givenName": "Michael", 
        "type": "Person"
      }, 
      {
        "familyName": "Tan", 
        "givenName": "Xuehou", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38756-2_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38755-5", 
        "978-3-642-38756-2"
      ], 
      "name": "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "set of species", 
      "rSPR distance", 
      "phylogenetic tree", 
      "different phylogenetic trees", 
      "number of leaves", 
      "hybridization events", 
      "different genes", 
      "regraft distance", 
      "subtree prune", 
      "Fast Exact Computation", 
      "species", 
      "trees", 
      "input trees", 
      "genes", 
      "leaves", 
      "evolution", 
      "dissimilarity", 
      "distance", 
      "events", 
      "number", 
      "prunes", 
      "set", 
      "experiments", 
      "software tools", 
      "tool", 
      "exact algorithm", 
      "time", 
      "fast exact algorithm", 
      "better software", 
      "new algorithm", 
      "algorithm", 
      "exact computation", 
      "new version", 
      "software", 
      "computation", 
      "purpose", 
      "version", 
      "cases", 
      "problem", 
      "paper"
    ], 
    "name": "Faster Exact Computation of rSPR Distance", 
    "pagination": "36-47", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048239420"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38756-2_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38756-2_7", 
      "https://app.dimensions.ai/details/publication/pub.1048239420"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:44", 
    "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_26.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38756-2_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.1007/978-3-642-38756-2_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.1007/978-3-642-38756-2_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38756-2_7'

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-642-38756-2_7'


 

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

120 TRIPLES      23 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38756-2_7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9a2bb6de212c4fe1bcf6ff90dbc6d4a4
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
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, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(2.415^dn\right)$\end{document} time, where n and d are the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(2.344^dn\right)$\end{document} time. Our experiments show that the new algorithm can be significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, Whidden et al.’s RSPR) for rSPR distance.
7 schema:editor N180275c892054275ac8a4fa8ffc0d75f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf75693b1cb2b4b30add3b07fd190b161
12 schema:keywords Fast Exact Computation
13 algorithm
14 better software
15 cases
16 computation
17 different genes
18 different phylogenetic trees
19 dissimilarity
20 distance
21 events
22 evolution
23 exact algorithm
24 exact computation
25 experiments
26 fast exact algorithm
27 genes
28 hybridization events
29 input trees
30 leaves
31 new algorithm
32 new version
33 number
34 number of leaves
35 paper
36 phylogenetic tree
37 problem
38 prunes
39 purpose
40 rSPR distance
41 regraft distance
42 set
43 set of species
44 software
45 software tools
46 species
47 subtree prune
48 time
49 tool
50 trees
51 version
52 schema:name Faster Exact Computation of rSPR Distance
53 schema:pagination 36-47
54 schema:productId N561b4ee0aef74d5792c077c8b7e28f3f
55 Naf3e508c851c4c50b9368cb37c90fe02
56 schema:publisher N28b17a64e9d344fd84665d91527a81f0
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048239420
58 https://doi.org/10.1007/978-3-642-38756-2_7
59 schema:sdDatePublished 2022-05-10T10:44
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N8eecb4bd78b34352b7b795666bba0eb6
62 schema:url https://doi.org/10.1007/978-3-642-38756-2_7
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N06d572afab19449a83a8b7909309a8e7 rdf:first Nd553b710bac940a5898dbcbae0afb8b9
67 rdf:rest Ne1037b51ddc145d482bc88d3ac9af539
68 N180275c892054275ac8a4fa8ffc0d75f rdf:first N21b7f71cce934a2cb65f79555df65487
69 rdf:rest N06d572afab19449a83a8b7909309a8e7
70 N21b7f71cce934a2cb65f79555df65487 schema:familyName Fellows
71 schema:givenName Michael
72 rdf:type schema:Person
73 N28b17a64e9d344fd84665d91527a81f0 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N3ca9682ee63d4e9985545fd31c9eb256 schema:familyName Zhu
76 schema:givenName Binhai
77 rdf:type schema:Person
78 N561b4ee0aef74d5792c077c8b7e28f3f schema:name dimensions_id
79 schema:value pub.1048239420
80 rdf:type schema:PropertyValue
81 N82a93aa07ea44a4983f649ea0dbf5b8d rdf:first sg:person.01105113721.52
82 rdf:rest rdf:nil
83 N8eecb4bd78b34352b7b795666bba0eb6 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 N9a2bb6de212c4fe1bcf6ff90dbc6d4a4 rdf:first sg:person.015654265661.98
86 rdf:rest N82a93aa07ea44a4983f649ea0dbf5b8d
87 Naf3e508c851c4c50b9368cb37c90fe02 schema:name doi
88 schema:value 10.1007/978-3-642-38756-2_7
89 rdf:type schema:PropertyValue
90 Nd553b710bac940a5898dbcbae0afb8b9 schema:familyName Tan
91 schema:givenName Xuehou
92 rdf:type schema:Person
93 Ne1037b51ddc145d482bc88d3ac9af539 rdf:first N3ca9682ee63d4e9985545fd31c9eb256
94 rdf:rest rdf:nil
95 Nf75693b1cb2b4b30add3b07fd190b161 schema:isbn 978-3-642-38755-5
96 978-3-642-38756-2
97 schema:name Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.01105113721.52 schema:affiliation grid-institutes:None
106 schema:familyName Wang
107 schema:givenName Lusheng
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
109 rdf:type schema:Person
110 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
111 schema:familyName Chen
112 schema:givenName Zhi-Zhong
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
114 rdf:type schema:Person
115 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
116 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
117 rdf:type schema:Organization
118 grid-institutes:grid.412773.4 schema:alternateName Department of Information System Design, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
119 schema:name Department of Information System Design, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
120 rdf:type schema:Organization
 




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


...