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 Nf42760faf1944ba08bfac9f094a38e72
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 N901ac9fdc99f4bd89b634afbf02b99f3
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf Nf034f1b1199147a3a639b2f1e83d9c44
20 schema:name A New Measure of Edit Distance between Labeled Trees
21 schema:pagination 338-348
22 schema:productId N62f893fb92b64f41a430642b8c410ceb
23 Ne153fe46b70644af8390238dc3dbcfb1
24 Nf66212e2ae7f433a8471bb19eb34c239
25 schema:publisher N28996bf3a24a4f0cb8d945d7b17cca7c
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 N831382572d7c4fb894477b5d544a6ed9
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 N28996bf3a24a4f0cb8d945d7b17cca7c schema:location Berlin, Heidelberg
36 schema:name Springer Berlin Heidelberg
37 rdf:type schema:Organisation
38 N62f893fb92b64f41a430642b8c410ceb schema:name dimensions_id
39 schema:value pub.1049040556
40 rdf:type schema:PropertyValue
41 N831382572d7c4fb894477b5d544a6ed9 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N901ac9fdc99f4bd89b634afbf02b99f3 rdf:first Na8d09d8e5b634720beccfe2552351a13
44 rdf:rest rdf:nil
45 Na8d09d8e5b634720beccfe2552351a13 schema:familyName Wang
46 schema:givenName Jie
47 rdf:type schema:Person
48 Ne153fe46b70644af8390238dc3dbcfb1 schema:name doi
49 schema:value 10.1007/3-540-44679-6_37
50 rdf:type schema:PropertyValue
51 Nea129d36760d4c0d9d866801f8470318 rdf:first sg:person.01312526135.27
52 rdf:rest rdf:nil
53 Nea9105f6e87d4c779071663871fc1e88 rdf:first sg:person.0732730317.59
54 rdf:rest Nea129d36760d4c0d9d866801f8470318
55 Nf034f1b1199147a3a639b2f1e83d9c44 schema:isbn 978-3-540-42494-9
56 978-3-540-44679-8
57 schema:name Computing and Combinatorics
58 rdf:type schema:Book
59 Nf42760faf1944ba08bfac9f094a38e72 rdf:first sg:person.016502771037.22
60 rdf:rest Nea9105f6e87d4c779071663871fc1e88
61 Nf66212e2ae7f433a8471bb19eb34c239 schema:name readcube_id
62 schema:value e99ef9470c5a38d80d288e05a38ca57e58d4928312c5cf0a186308448e6365c7
63 rdf:type schema:PropertyValue
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)


...