2013-12-08
AUTHORSZhi-Zhong Chen, Ying Fan, Lusheng Wang
ABSTRACTDue 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 O2.415dn\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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} and d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d$$\end{document} 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 O2.344dn\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 is significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, rSPR) for RSPR distance. More... »
PAGES605-635
http://scigraph.springernature.com/pub.10.1007/s10878-013-9695-8
DOIhttp://dx.doi.org/10.1007/s10878-013-9695-8
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1001021632
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, 359-0394, Hiki, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, 359-0394, Hiki, 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": "Fan",
"givenName": "Ying",
"id": "sg:person.016605774033.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016605774033.37"
],
"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"
}
],
"citation": [
{
"id": "sg:pub.10.1186/1471-2105-13-155",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013236358",
"https://doi.org/10.1186/1471-2105-13-155"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1186/1471-2148-6-15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031420454",
"https://doi.org/10.1186/1471-2148-6-15"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1009833626004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002933561",
"https://doi.org/10.1023/a:1009833626004"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1186/1471-2105-9-322",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007573310",
"https://doi.org/10.1186/1471-2105-9-322"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1186/1471-2148-10-42",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017964138",
"https://doi.org/10.1186/1471-2148-10-42"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1186/1471-2148-5-27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041618709",
"https://doi.org/10.1186/1471-2148-5-27"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1009837726913",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039984867",
"https://doi.org/10.1023/a:1009837726913"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10878-009-9261-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011030000",
"https://doi.org/10.1007/s10878-009-9261-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-04241-6_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053482868",
"https://doi.org/10.1007/978-3-642-04241-6_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-13193-6_13",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021203456",
"https://doi.org/10.1007/978-3-642-13193-6_13"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00026-004-0229-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049592483",
"https://doi.org/10.1007/s00026-004-0229-z"
],
"type": "CreativeWork"
}
],
"datePublished": "2013-12-08",
"datePublishedReg": "2013-12-08",
"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 O2.415dn\\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\\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}$$n$$\\end{document} and d\\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}$$d$$\\end{document} 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 O2.344dn\\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 is significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, rSPR) for RSPR distance.",
"genre": "article",
"id": "sg:pub.10.1007/s10878-013-9695-8",
"inLanguage": "en",
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.7427614",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.6078852",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1036683",
"issn": [
"1382-6905",
"1573-2886"
],
"name": "Journal of Combinatorial Optimization",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "29"
}
],
"keywords": [
"set of species",
"rSPR distance",
"phylogenetic tree",
"different phylogenetic trees",
"number of leaves",
"hybridization events",
"different genes",
"regraft distance",
"subtree prune",
"species",
"trees",
"input trees",
"genes",
"leaves",
"evolution",
"dissimilarity",
"distance",
"events",
"number",
"set",
"prunes",
"experiments",
"software tools",
"tool",
"time",
"fast exact algorithm",
"new version",
"better software",
"purpose",
"version",
"cases",
"exact algorithm",
"software",
"problem",
"new algorithm",
"algorithm",
"paper",
"exact computation",
"computation"
],
"name": "Faster exact computation of rSPR distance",
"pagination": "605-635",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1001021632"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10878-013-9695-8"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10878-013-9695-8",
"https://app.dimensions.ai/details/publication/pub.1001021632"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:28",
"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/article/article_585.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s10878-013-9695-8"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10878-013-9695-8'
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/s10878-013-9695-8'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-013-9695-8'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-013-9695-8'
This table displays all metadata directly associated to this object as RDF triples.
170 TRIPLES
22 PREDICATES
77 URIs
56 LITERALS
6 BLANK NODES