Some notes on the nearest neighbour interchange distance View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1996

AUTHORS

Ming Li , John Tromp , Louxin Zhang

ABSTRACT

We present some new results on a well known distance measure between evolutionary trees. The trees we consider are free 3-trees having n leaves labeled 0,..., n − 1 (representing species), and n − 2 internal nodes of degree 3. The distance between two trees is the minimum number of nearest neighbour interchange (NNI) operations required to transform one into the other. First, we improve an upper bound on the nni-distance between two arbitrary n-node trees from 4n log n [2] to n log n. Second, we present a counterexample disproving several theorems in [13]. Roughly speaking, finding an equal partition between two trees doesn't imply decomposability of the distance finding problem. Third, we present a polynomial-time approximation algorithm that, given two trees, finds a transformation between them of length O(log n) times their distance. We also present some results of computations we performed on small size trees. More... »

PAGES

343-351

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-61332-9
978-3-540-68461-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61332-3_168

DOI

http://dx.doi.org/10.1007/3-540-61332-3_168

DIMENSIONS

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


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/0604", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Genetics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, N2L 3G1\u00a0Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Ming", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, N2L 3G1\u00a0Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tromp", 
        "givenName": "John", 
        "id": "sg:person.011226061741.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, N2L 3G1\u00a0Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Louxin", 
        "id": "sg:person.012763757651.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012763757651.13"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0022-5193(78)90137-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025558724"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-5193(73)90251-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041607308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We present some new results on a well known distance measure between evolutionary trees. The trees we consider are free 3-trees having n leaves labeled 0,..., n \u2212 1 (representing species), and n \u2212 2 internal nodes of degree 3. The distance between two trees is the minimum number of nearest neighbour interchange (NNI) operations required to transform one into the other. First, we improve an upper bound on the nni-distance between two arbitrary n-node trees from 4n log n [2] to n log n. Second, we present a counterexample disproving several theorems in [13]. Roughly speaking, finding an equal partition between two trees doesn't imply decomposability of the distance finding problem. Third, we present a polynomial-time approximation algorithm that, given two trees, finds a transformation between them of length O(log n) times their distance. We also present some results of computations we performed on small size trees.", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Jin-Yi", 
        "type": "Person"
      }, 
      {
        "familyName": "Wong", 
        "givenName": "Chak Kuen", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61332-3_168", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61332-9", 
        "978-3-540-68461-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Some notes on the nearest neighbour interchange distance", 
    "pagination": "343-351", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61332-3_168"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d32ab118f0351c9a7cb77ec32e4075f137a81d4ce1fddb4f7172dd8948dd0a4a"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044331451"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61332-3_168", 
      "https://app.dimensions.ai/details/publication/pub.1044331451"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T20:08", 
    "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_8687_00000270.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-61332-3_168"
  }
]
 

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-61332-3_168'

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-61332-3_168'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-61332-3_168'

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-61332-3_168'


 

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

93 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61332-3_168 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author N65726536b55a42c5ac6d915ba7206cad
4 schema:citation https://doi.org/10.1016/0022-0000(91)90023-x
5 https://doi.org/10.1016/0022-5193(73)90251-8
6 https://doi.org/10.1016/0022-5193(78)90137-6
7 schema:datePublished 1996
8 schema:datePublishedReg 1996-01-01
9 schema:description We present some new results on a well known distance measure between evolutionary trees. The trees we consider are free 3-trees having n leaves labeled 0,..., n − 1 (representing species), and n − 2 internal nodes of degree 3. The distance between two trees is the minimum number of nearest neighbour interchange (NNI) operations required to transform one into the other. First, we improve an upper bound on the nni-distance between two arbitrary n-node trees from 4n log n [2] to n log n. Second, we present a counterexample disproving several theorems in [13]. Roughly speaking, finding an equal partition between two trees doesn't imply decomposability of the distance finding problem. Third, we present a polynomial-time approximation algorithm that, given two trees, finds a transformation between them of length O(log n) times their distance. We also present some results of computations we performed on small size trees.
10 schema:editor N8db83a62fc3d4c9d809b462c7079d64c
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf Nacfd845178374a4690220c0a92aa519e
15 schema:name Some notes on the nearest neighbour interchange distance
16 schema:pagination 343-351
17 schema:productId N00e7b7e44fc74f86b24896085285b016
18 Nae3911f5dee84f2a9ca6d49ea8117b24
19 Nb3fb4d98c52e49ccbd65b5cc3532135b
20 schema:publisher Nb878bbd838df488184e19f38a6011491
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044331451
22 https://doi.org/10.1007/3-540-61332-3_168
23 schema:sdDatePublished 2019-04-15T20:08
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher N59b9c9e6b52e4827a0d02ba2ca6a6cfc
26 schema:url http://link.springer.com/10.1007/3-540-61332-3_168
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N00e7b7e44fc74f86b24896085285b016 schema:name readcube_id
31 schema:value d32ab118f0351c9a7cb77ec32e4075f137a81d4ce1fddb4f7172dd8948dd0a4a
32 rdf:type schema:PropertyValue
33 N1e19e1a3705f4691bf1ead26a5bc1827 rdf:first N406a9009c4434c0b988645f652400e6c
34 rdf:rest rdf:nil
35 N36f4eb10fd5c40a08666639b20eb3a1c rdf:first sg:person.011226061741.52
36 rdf:rest N7d7bb9a8237f471bbd129cda7a78f56f
37 N406a9009c4434c0b988645f652400e6c schema:familyName Wong
38 schema:givenName Chak Kuen
39 rdf:type schema:Person
40 N59b9c9e6b52e4827a0d02ba2ca6a6cfc schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N5c6a8c126cd9428c807e1b4d182c2cf6 schema:familyName Cai
43 schema:givenName Jin-Yi
44 rdf:type schema:Person
45 N65726536b55a42c5ac6d915ba7206cad rdf:first sg:person.0621576316.79
46 rdf:rest N36f4eb10fd5c40a08666639b20eb3a1c
47 N7d7bb9a8237f471bbd129cda7a78f56f rdf:first sg:person.012763757651.13
48 rdf:rest rdf:nil
49 N8db83a62fc3d4c9d809b462c7079d64c rdf:first N5c6a8c126cd9428c807e1b4d182c2cf6
50 rdf:rest N1e19e1a3705f4691bf1ead26a5bc1827
51 Nacfd845178374a4690220c0a92aa519e schema:isbn 978-3-540-61332-9
52 978-3-540-68461-9
53 schema:name Computing and Combinatorics
54 rdf:type schema:Book
55 Nae3911f5dee84f2a9ca6d49ea8117b24 schema:name dimensions_id
56 schema:value pub.1044331451
57 rdf:type schema:PropertyValue
58 Nb3fb4d98c52e49ccbd65b5cc3532135b schema:name doi
59 schema:value 10.1007/3-540-61332-3_168
60 rdf:type schema:PropertyValue
61 Nb878bbd838df488184e19f38a6011491 schema:location Berlin, Heidelberg
62 schema:name Springer Berlin Heidelberg
63 rdf:type schema:Organisation
64 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
65 schema:name Biological Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
68 schema:name Genetics
69 rdf:type schema:DefinedTerm
70 sg:person.011226061741.52 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
71 schema:familyName Tromp
72 schema:givenName John
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52
74 rdf:type schema:Person
75 sg:person.012763757651.13 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
76 schema:familyName Zhang
77 schema:givenName Louxin
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012763757651.13
79 rdf:type schema:Person
80 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
81 schema:familyName Li
82 schema:givenName Ming
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
84 rdf:type schema:Person
85 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/0022-5193(73)90251-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041607308
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1016/0022-5193(78)90137-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025558724
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
92 schema:name Department of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ont., Canada
93 rdf:type schema:Organization
 




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


...