A New Measure of Edit Distance between Labeled Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-07-31

AUTHORS

Chin Lung Lu , Zheng-Yao Su , Chuan Yi Tang

ABSTRACT

One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem. More... »

PAGES

338-348

References to SciGraph publications

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-42494-9
978-3-540-44679-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44679-6_37

DOI

http://dx.doi.org/10.1007/3-540-44679-6_37

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Center for High-Performance Computing", 
          "id": "https://www.grid.ac/institutes/grid.462649.b", 
          "name": [
            "National Center for High-Performance Computing, 19-136, 300, Hsinchu, R.O.C., Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Chin Lung", 
        "id": "sg:person.016502771037.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Center for High-Performance Computing", 
          "id": "https://www.grid.ac/institutes/grid.462649.b", 
          "name": [
            "National Center for High-Performance Computing, 19-136, 300, Hsinchu, R.O.C., Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Su", 
        "givenName": "Zheng-Yao", 
        "id": "sg:person.0732730317.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0732730317.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, 300, Hsinchu, R.O.C., Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(92)90136-j", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016602097"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/278298.278306", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022637686"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(94)00109-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033025568"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01975866", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033832980", 
          "https://doi.org/10.1007/bf01975866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01975866", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033832980", 
          "https://doi.org/10.1007/bf01975866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(94)90062-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035113856"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(91)90246-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045676358"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218082", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842181"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218001488000157", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062950606"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001-07-31", 
    "datePublishedReg": "2001-07-31", 
    "description": "One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.", 
    "editor": [
      {
        "familyName": "Wang", 
        "givenName": "Jie", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44679-6_37", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42494-9", 
        "978-3-540-44679-8"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "A New Measure of Edit Distance between Labeled Trees", 
    "pagination": "338-348", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44679-6_37"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e99ef9470c5a38d80d288e05a38ca57e58d4928312c5cf0a186308448e6365c7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049040556"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44679-6_37", 
      "https://app.dimensions.ai/details/publication/pub.1049040556"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:36", 
    "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/0000000346_0000000346/records_99832_00000003.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-44679-6_37"
  }
]
 

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-44679-6_37'

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-44679-6_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44679-6_37'

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-44679-6_37'


 

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

107 TRIPLES      23 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44679-6_37 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5efd5f4380aa4c56bcb955de0cfcf9e9
4 schema:citation sg:pub.10.1007/bf01975866
5 https://doi.org/10.1016/0020-0190(91)90246-e
6 https://doi.org/10.1016/0020-0190(92)90136-j
7 https://doi.org/10.1016/0020-0190(94)90062-0
8 https://doi.org/10.1016/0031-3203(94)00109-y
9 https://doi.org/10.1137/0218082
10 https://doi.org/10.1142/s0218001488000157
11 https://doi.org/10.1145/278298.278306
12 schema:datePublished 2001-07-31
13 schema:datePublishedReg 2001-07-31
14 schema:description One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.
15 schema:editor Ne16e9c86896042b9a7c4d051e41bf5e8
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N74816a37fe1040eb8a61fb8dcb1aa600
20 schema:name A New Measure of Edit Distance between Labeled Trees
21 schema:pagination 338-348
22 schema:productId N1bf8aa4c5d374db09ea5b5f707842664
23 N3643275217734b2393990900562f34ab
24 N536a4e876e074176a7def4344a8de968
25 schema:publisher N18e2914b6ed24554b8f520e372eccd10
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049040556
27 https://doi.org/10.1007/3-540-44679-6_37
28 schema:sdDatePublished 2019-04-16T05:36
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N62b92448b8f2492fab3009120f10cd04
31 schema:url https://link.springer.com/10.1007%2F3-540-44679-6_37
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0125bff024f54169b0103b7c711b8951 rdf:first sg:person.01312526135.27
36 rdf:rest rdf:nil
37 N18e2914b6ed24554b8f520e372eccd10 schema:location Berlin, Heidelberg
38 schema:name Springer Berlin Heidelberg
39 rdf:type schema:Organisation
40 N1bf8aa4c5d374db09ea5b5f707842664 schema:name readcube_id
41 schema:value e99ef9470c5a38d80d288e05a38ca57e58d4928312c5cf0a186308448e6365c7
42 rdf:type schema:PropertyValue
43 N3643275217734b2393990900562f34ab schema:name doi
44 schema:value 10.1007/3-540-44679-6_37
45 rdf:type schema:PropertyValue
46 N536a4e876e074176a7def4344a8de968 schema:name dimensions_id
47 schema:value pub.1049040556
48 rdf:type schema:PropertyValue
49 N5efd5f4380aa4c56bcb955de0cfcf9e9 rdf:first sg:person.016502771037.22
50 rdf:rest Nca5c0ce7a9e74ce3b5c738f4b9f40fea
51 N62b92448b8f2492fab3009120f10cd04 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N74816a37fe1040eb8a61fb8dcb1aa600 schema:isbn 978-3-540-42494-9
54 978-3-540-44679-8
55 schema:name Computing and Combinatorics
56 rdf:type schema:Book
57 N919303125c8e44aa99cebb53281093e6 schema:familyName Wang
58 schema:givenName Jie
59 rdf:type schema:Person
60 Nca5c0ce7a9e74ce3b5c738f4b9f40fea rdf:first sg:person.0732730317.59
61 rdf:rest N0125bff024f54169b0103b7c711b8951
62 Ne16e9c86896042b9a7c4d051e41bf5e8 rdf:first N919303125c8e44aa99cebb53281093e6
63 rdf:rest rdf:nil
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
71 schema:familyName Tang
72 schema:givenName Chuan Yi
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
74 rdf:type schema:Person
75 sg:person.016502771037.22 schema:affiliation https://www.grid.ac/institutes/grid.462649.b
76 schema:familyName Lu
77 schema:givenName Chin Lung
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22
79 rdf:type schema:Person
80 sg:person.0732730317.59 schema:affiliation https://www.grid.ac/institutes/grid.462649.b
81 schema:familyName Su
82 schema:givenName Zheng-Yao
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0732730317.59
84 rdf:type schema:Person
85 sg:pub.10.1007/bf01975866 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033832980
86 https://doi.org/10.1007/bf01975866
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1016/0020-0190(91)90246-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1045676358
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/0020-0190(92)90136-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1016602097
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0020-0190(94)90062-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035113856
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0031-3203(94)00109-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1033025568
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1137/0218082 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842181
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1142/s0218001488000157 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062950606
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1145/278298.278306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022637686
101 rdf:type schema:CreativeWork
102 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
103 schema:name Department of Computer Science, National Tsing Hua University, 300, Hsinchu, R.O.C., Taiwan
104 rdf:type schema:Organization
105 https://www.grid.ac/institutes/grid.462649.b schema:alternateName National Center for High-Performance Computing
106 schema:name National Center for High-Performance Computing, 19-136, 300, Hsinchu, R.O.C., Taiwan
107 rdf:type schema:Organization
 




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


...