On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1999-06

AUTHORS

B. DasGupta, X. He, T. Jiang, M. Li, J. Tromp

ABSTRACT

Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [16] or from different genes [12] in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities (i.e., distance ) is thus an important issue in computational molecular biology. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexity and efficient approximation algorithms for this distance as well as its relationship to the nni distance. The linear-cost subtree-transfer model seems more suitable than the (unit-cost) subtree-transfer model in some applications. The following is a list of our results: 1. The linear-cost subtree-transfer distance is in fact identical to the nni distance on unweighted phylogenies. 2. There is an algorithm to compute an optimal linear-cost subtree-transfer sequence between unweighted phylogenies in O(n⋅2O(d)) time, where d denotes the linear-cost subtree-transfer distance. Such an algorithm is useful when d is small. 3. Computing the linear-cost subtree-transfer distance between two weighted phylogenetic trees is NP-hard, provided we allow multiple leaves of a tree to share the same label (i.e., the trees are not necessarily uniquely labeled). 4. There is an efficient approximation algorithm for computing the linear-cost subtree-transfer distance between weighted phylogenies with performance ratio 2 . More... »

PAGES

176-195

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/pl00008273

DOI

http://dx.doi.org/10.1007/pl00008273

DIMENSIONS

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


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/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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, Camden, NJ 08102, USA. bhaskar@crab.rutgers.edu., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "B.", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University at Buffalo, State University of New York", 
          "id": "https://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, SUNY-Buffalo, Buffalo, NY 14260, USA. xinhe@cs.buffalo.edu., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "X.", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "McMaster University", 
          "id": "https://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Department of Computer Science, McMaster University, Hamilton, Ontario, Canada L8S 4K1.  jiang@maccs.mcmaster.ca., CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "T.", 
        "id": "sg:person.011617335564.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. mli@math.uwaterloo.ca., CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "M.", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Centrum Wiskunde and Informatica", 
          "id": "https://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. tromp@cwi.nl., NL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tromp", 
        "givenName": "J.", 
        "id": "sg:person.011226061741.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-06", 
    "datePublishedReg": "1999-06-01", 
    "description": "Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [16] or from different genes [12] in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities (i.e., distance ) is thus an important issue in computational molecular biology. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexity and efficient approximation algorithms for this distance as well as its relationship to the nni distance. The linear-cost subtree-transfer model seems more suitable than the (unit-cost) subtree-transfer model in some applications. The following is a list of our results:  1. The linear-cost subtree-transfer distance is in fact identical to the nni distance on unweighted phylogenies.  2. There is an algorithm to compute an optimal linear-cost subtree-transfer sequence between unweighted phylogenies in O(n\u22c52O(d)) time, where d denotes the linear-cost subtree-transfer distance. Such an algorithm is useful when d is small.  3. Computing the linear-cost subtree-transfer distance between two weighted phylogenetic trees is NP-hard, provided we allow multiple leaves of a tree to share the same label (i.e., the trees are not necessarily uniquely labeled).  4. There is an efficient approximation algorithm for computing the linear-cost subtree-transfer distance between weighted phylogenies with performance ratio 2 . ", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/pl00008273", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "25"
      }
    ], 
    "name": "On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees", 
    "pagination": "176-195", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f38eb8bf8e34461749c85a53dcbbcea682f62eec12b9d6296ea811ce24b49b06"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/pl00008273"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051128576"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/pl00008273", 
      "https://app.dimensions.ai/details/publication/pub.1051128576"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T22:33", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8690_00000516.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FPL00008273"
  }
]
 

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/pl00008273'

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/pl00008273'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/pl00008273'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/pl00008273'


 

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

101 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/pl00008273 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N55f9da869d3347e48f6b266a70f60d5a
4 schema:datePublished 1999-06
5 schema:datePublishedReg 1999-06-01
6 schema:description Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [16] or from different genes [12] in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities (i.e., distance ) is thus an important issue in computational molecular biology. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexity and efficient approximation algorithms for this distance as well as its relationship to the nni distance. The linear-cost subtree-transfer model seems more suitable than the (unit-cost) subtree-transfer model in some applications. The following is a list of our results: 1. The linear-cost subtree-transfer distance is in fact identical to the nni distance on unweighted phylogenies. 2. There is an algorithm to compute an optimal linear-cost subtree-transfer sequence between unweighted phylogenies in O(n⋅2O(d)) time, where d denotes the linear-cost subtree-transfer distance. Such an algorithm is useful when d is small. 3. Computing the linear-cost subtree-transfer distance between two weighted phylogenetic trees is NP-hard, provided we allow multiple leaves of a tree to share the same label (i.e., the trees are not necessarily uniquely labeled). 4. There is an efficient approximation algorithm for computing the linear-cost subtree-transfer distance between weighted phylogenies with performance ratio 2 .
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf Nc0916b6e98a6400c91b9ba7c4382cb04
11 Nc54741a9f8164440aca578f88418f750
12 sg:journal.1047644
13 schema:name On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees
14 schema:pagination 176-195
15 schema:productId N32124746829b4e009b4e5f7d1ebfbe8e
16 Nb2508394f6524e93ad53e3895fc9ade0
17 Nf0ff26a6ee80491bb78341c50c4e6b26
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051128576
19 https://doi.org/10.1007/pl00008273
20 schema:sdDatePublished 2019-04-10T22:33
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N658fd8f541b84aa9bf760a7e6087b06b
23 schema:url http://link.springer.com/10.1007%2FPL00008273
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N32124746829b4e009b4e5f7d1ebfbe8e schema:name doi
28 schema:value 10.1007/pl00008273
29 rdf:type schema:PropertyValue
30 N38423615f1d64987a804885580580901 rdf:first sg:person.0621576316.79
31 rdf:rest N9bf04e4451d842b58b24d06c3a4be165
32 N55f9da869d3347e48f6b266a70f60d5a rdf:first sg:person.0763403270.10
33 rdf:rest N9b39ee9b3f2a461c8b1f235bdacc0cb7
34 N658fd8f541b84aa9bf760a7e6087b06b schema:name Springer Nature - SN SciGraph project
35 rdf:type schema:Organization
36 N8c1906222e7d4f1da8c4de823499ddfa rdf:first sg:person.011617335564.48
37 rdf:rest N38423615f1d64987a804885580580901
38 N9b39ee9b3f2a461c8b1f235bdacc0cb7 rdf:first sg:person.011352641523.42
39 rdf:rest N8c1906222e7d4f1da8c4de823499ddfa
40 N9bf04e4451d842b58b24d06c3a4be165 rdf:first sg:person.011226061741.52
41 rdf:rest rdf:nil
42 Nb2508394f6524e93ad53e3895fc9ade0 schema:name readcube_id
43 schema:value f38eb8bf8e34461749c85a53dcbbcea682f62eec12b9d6296ea811ce24b49b06
44 rdf:type schema:PropertyValue
45 Nc0916b6e98a6400c91b9ba7c4382cb04 schema:volumeNumber 25
46 rdf:type schema:PublicationVolume
47 Nc54741a9f8164440aca578f88418f750 schema:issueNumber 2-3
48 rdf:type schema:PublicationIssue
49 Nf0ff26a6ee80491bb78341c50c4e6b26 schema:name dimensions_id
50 schema:value pub.1051128576
51 rdf:type schema:PropertyValue
52 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
53 schema:name Mathematical Sciences
54 rdf:type schema:DefinedTerm
55 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
56 schema:name Applied Mathematics
57 rdf:type schema:DefinedTerm
58 sg:journal.1047644 schema:issn 0178-4617
59 1432-0541
60 schema:name Algorithmica
61 rdf:type schema:Periodical
62 sg:person.011226061741.52 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
63 schema:familyName Tromp
64 schema:givenName J.
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52
66 rdf:type schema:Person
67 sg:person.011352641523.42 schema:affiliation https://www.grid.ac/institutes/grid.273335.3
68 schema:familyName He
69 schema:givenName X.
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
71 rdf:type schema:Person
72 sg:person.011617335564.48 schema:affiliation https://www.grid.ac/institutes/grid.25073.33
73 schema:familyName Jiang
74 schema:givenName T.
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48
76 rdf:type schema:Person
77 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
78 schema:familyName Li
79 schema:givenName M.
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
81 rdf:type schema:Person
82 sg:person.0763403270.10 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
83 schema:familyName DasGupta
84 schema:givenName B.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
86 rdf:type schema:Person
87 https://www.grid.ac/institutes/grid.25073.33 schema:alternateName McMaster University
88 schema:name Department of Computer Science, McMaster University, Hamilton, Ontario, Canada L8S 4K1. jiang@maccs.mcmaster.ca., CA
89 rdf:type schema:Organization
90 https://www.grid.ac/institutes/grid.273335.3 schema:alternateName University at Buffalo, State University of New York
91 schema:name Department of Computer Science, SUNY-Buffalo, Buffalo, NY 14260, USA. xinhe@cs.buffalo.edu., US
92 rdf:type schema:Organization
93 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
94 schema:name Department of Computer Science, Rutgers University, Camden, NJ 08102, USA. bhaskar@crab.rutgers.edu., US
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
97 schema:name Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. mli@math.uwaterloo.ca., CA
98 rdf:type schema:Organization
99 https://www.grid.ac/institutes/grid.6054.7 schema:alternateName Centrum Wiskunde and Informatica
100 schema:name CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. tromp@cwi.nl., NL
101 rdf:type schema:Organization
 




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


...