The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-07-04

AUTHORS

Guo-Hui Lin , Zhi-Zhong Chen , Tao Jiang , Jianjun Wen

ABSTRACT

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The LONGEST ARC- PRESERVING COMMON SUBSEQUENCE (LAPCS) Problem has been introduced in [11] as a framework for studying the similarity of arc-annotated sequences. Several algorithmic and complexity results on the LAPCS problem have been presented in [1117]. In this paper, we continue this line of research and present new algorithmic and complexity results on the LAPCS problem restricted to two nested arc-annotated sequences, denoted as LAPCS(NESTED, NESTED). The restricted problem is perhaps the most interesting variant of the LAPCS problem and has important applications in the comparison of RNA secondary and tertiary structures. Particularly, we prove that LAPCS(NESTED, NESTED) is NP-hard, which answers an open question in [11]. We then present a polynomial-time approximation scheme for LAPCS(NESTED, NESTED) with an additional c- diagonal restriction. An interesting special case, upunary LAPCS(NESTED, NESTED), is also investigated. More... »

PAGES

444-455

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48224-5_37

DOI

http://dx.doi.org/10.1007/3-540-48224-5_37

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada", 
            "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Guo-Hui", 
        "id": "sg:person.01130357621.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, 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, University of California, 92521, Riverside, CA", 
          "id": "http://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada", 
            "Department of Computer Science, University of California, 92521, Riverside, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.015107424575.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of California, 92521, Riverside, CA", 
          "id": "http://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Department of Computer Science, University of California, 92521, Riverside, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wen", 
        "givenName": "Jianjun", 
        "id": "sg:person.013667114745.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667114745.67"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-07-04", 
    "datePublishedReg": "2001-07-04", 
    "description": "Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The LONGEST ARC- PRESERVING COMMON SUBSEQUENCE (LAPCS) Problem has been introduced in [11] as a framework for studying the similarity of arc-annotated sequences. Several algorithmic and complexity results on the LAPCS problem have been presented in [1117]. In this paper, we continue this line of research and present new algorithmic and complexity results on the LAPCS problem restricted to two nested arc-annotated sequences, denoted as LAPCS(NESTED, NESTED). The restricted problem is perhaps the most interesting variant of the LAPCS problem and has important applications in the comparison of RNA secondary and tertiary structures. Particularly, we prove that LAPCS(NESTED, NESTED) is NP-hard, which answers an open question in [11]. We then present a polynomial-time approximation scheme for LAPCS(NESTED, NESTED) with an additional c- diagonal restriction. An interesting special case, upunary LAPCS(NESTED, NESTED), is also investigated.", 
    "editor": [
      {
        "familyName": "Orejas", 
        "givenName": "Fernando", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48224-5_37", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42287-7", 
        "978-3-540-48224-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "arc-annotated sequences", 
      "common subsequence problem", 
      "complexity results", 
      "subsequence problem", 
      "polynomial time approximation scheme", 
      "longest common subsequence problem", 
      "diagonal restriction", 
      "important applications", 
      "interesting variant", 
      "approximation scheme", 
      "interesting special cases", 
      "line of research", 
      "structural information", 
      "annotation", 
      "protein sequences", 
      "NPs", 
      "scheme", 
      "framework", 
      "special case", 
      "information", 
      "open question", 
      "applications", 
      "sequence", 
      "similarity", 
      "results", 
      "research", 
      "variants", 
      "restriction", 
      "comparison", 
      "questions", 
      "structure", 
      "cases", 
      "lines", 
      "tertiary structure", 
      "Comparison of RNA", 
      "RNA", 
      "problem", 
      "paper"
    ], 
    "name": "The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations", 
    "pagination": "444-455", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027497758"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48224-5_37"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48224-5_37", 
      "https://app.dimensions.ai/details/publication/pub.1027497758"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:49", 
    "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/chapter/chapter_59.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48224-5_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-48224-5_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-48224-5_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_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-48224-5_37'


 

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

137 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48224-5_37 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9e5b5ac52a4741939b545843f63f03c5
4 schema:datePublished 2001-07-04
5 schema:datePublishedReg 2001-07-04
6 schema:description Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The LONGEST ARC- PRESERVING COMMON SUBSEQUENCE (LAPCS) Problem has been introduced in [11] as a framework for studying the similarity of arc-annotated sequences. Several algorithmic and complexity results on the LAPCS problem have been presented in [1117]. In this paper, we continue this line of research and present new algorithmic and complexity results on the LAPCS problem restricted to two nested arc-annotated sequences, denoted as LAPCS(NESTED, NESTED). The restricted problem is perhaps the most interesting variant of the LAPCS problem and has important applications in the comparison of RNA secondary and tertiary structures. Particularly, we prove that LAPCS(NESTED, NESTED) is NP-hard, which answers an open question in [11]. We then present a polynomial-time approximation scheme for LAPCS(NESTED, NESTED) with an additional c- diagonal restriction. An interesting special case, upunary LAPCS(NESTED, NESTED), is also investigated.
7 schema:editor Nda3cc5636d06424d83856903a7768849
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne8faa74a70fb4519abc650d27cd65787
12 schema:keywords Comparison of RNA
13 NPs
14 RNA
15 annotation
16 applications
17 approximation scheme
18 arc-annotated sequences
19 cases
20 common subsequence problem
21 comparison
22 complexity results
23 diagonal restriction
24 framework
25 important applications
26 information
27 interesting special cases
28 interesting variant
29 line of research
30 lines
31 longest common subsequence problem
32 open question
33 paper
34 polynomial time approximation scheme
35 problem
36 protein sequences
37 questions
38 research
39 restriction
40 results
41 scheme
42 sequence
43 similarity
44 special case
45 structural information
46 structure
47 subsequence problem
48 tertiary structure
49 variants
50 schema:name The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations
51 schema:pagination 444-455
52 schema:productId N293c2dd2795643c9b2a31745d056c0f2
53 N436c938719a1417b93ed00bfdec1d28e
54 schema:publisher Ne682bc0c872b4517b5b2f9fafdbe43be
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027497758
56 https://doi.org/10.1007/3-540-48224-5_37
57 schema:sdDatePublished 2022-05-20T07:49
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N1ef8f512b2864d5da9359dddab95b227
60 schema:url https://doi.org/10.1007/3-540-48224-5_37
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N1ef8f512b2864d5da9359dddab95b227 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N293c2dd2795643c9b2a31745d056c0f2 schema:name dimensions_id
67 schema:value pub.1027497758
68 rdf:type schema:PropertyValue
69 N384a9a04864c45038c77ea93e067e492 schema:familyName Orejas
70 schema:givenName Fernando
71 rdf:type schema:Person
72 N3d8e0c3bec6d4fb29835a8e8925e07a8 schema:familyName van Leeuwen
73 schema:givenName Jan
74 rdf:type schema:Person
75 N3e807d069734442cb4c07324fbf0f1f8 rdf:first N3d8e0c3bec6d4fb29835a8e8925e07a8
76 rdf:rest rdf:nil
77 N436c938719a1417b93ed00bfdec1d28e schema:name doi
78 schema:value 10.1007/3-540-48224-5_37
79 rdf:type schema:PropertyValue
80 N9131775899a543cd98203499a738f192 schema:familyName Spirakis
81 schema:givenName Paul G.
82 rdf:type schema:Person
83 N9e5b5ac52a4741939b545843f63f03c5 rdf:first sg:person.01130357621.02
84 rdf:rest Nabe1bd3ee8804566bc3b8dff043faa6c
85 Na54ed69f637348fbb15e0470d07d05ed rdf:first sg:person.013667114745.67
86 rdf:rest rdf:nil
87 Nabe1bd3ee8804566bc3b8dff043faa6c rdf:first sg:person.015654265661.98
88 rdf:rest Nca01aa25510f479fb52698a7517c78a6
89 Nc7fc86bc7fb54f78bd95720e2064e255 rdf:first N9131775899a543cd98203499a738f192
90 rdf:rest N3e807d069734442cb4c07324fbf0f1f8
91 Nca01aa25510f479fb52698a7517c78a6 rdf:first sg:person.015107424575.17
92 rdf:rest Na54ed69f637348fbb15e0470d07d05ed
93 Nda3cc5636d06424d83856903a7768849 rdf:first N384a9a04864c45038c77ea93e067e492
94 rdf:rest Nc7fc86bc7fb54f78bd95720e2064e255
95 Ne682bc0c872b4517b5b2f9fafdbe43be schema:name Springer Nature
96 rdf:type schema:Organisation
97 Ne8faa74a70fb4519abc650d27cd65787 schema:isbn 978-3-540-42287-7
98 978-3-540-48224-6
99 schema:name Automata, Languages and Programming
100 rdf:type schema:Book
101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
102 schema:name Information and Computing Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
105 schema:name Computation Theory and Mathematics
106 rdf:type schema:DefinedTerm
107 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.25073.33
108 schema:familyName Lin
109 schema:givenName Guo-Hui
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
111 rdf:type schema:Person
112 sg:person.013667114745.67 schema:affiliation grid-institutes:grid.266097.c
113 schema:familyName Wen
114 schema:givenName Jianjun
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667114745.67
116 rdf:type schema:Person
117 sg:person.015107424575.17 schema:affiliation grid-institutes:grid.266097.c
118 schema:familyName Jiang
119 schema:givenName Tao
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17
121 rdf:type schema:Person
122 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
123 schema:familyName Chen
124 schema:givenName Zhi-Zhong
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
126 rdf:type schema:Person
127 grid-institutes:grid.25073.33 schema:alternateName Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
128 schema:name Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
129 Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
130 rdf:type schema:Organization
131 grid-institutes:grid.266097.c schema:alternateName Department of Computer Science, University of California, 92521, Riverside, CA
132 schema:name Department of Computer Science, University of California, 92521, Riverside, CA
133 Department of Computing and Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada
134 rdf:type schema:Organization
135 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
136 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
137 rdf:type schema:Organization
 




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


...