Computing Similarity between RNA Structures

Kaizhong Zhang; Lusheng Wang; Bin Ma

doi:10.1007/3-540-48452-3_21

Computing Similarity between RNA Structures

Kaizhong Zhang, Lusheng Wang, Bin Ma

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

38 Citations (Scopus)

Abstract

The primary structure of a ribonucleic acid (RNA) molecule is a sequence of nucleotides (bases) over the alphabet {A,C,G,U}. The secondary or tertiary structure of an RNA is a set of base-pairs (nucleotide pairs) which forms bonds between A − U and C − G. For secondary structures, these bonds have been traditionally assumed to be one-to-one and non-crossing. This paper considers a notion of similarity between two RNA molecule structures taking into account the primary, the secondary and the tertiary structures. We show that in general this problem is NP-hard for tertiary structures. We present algorithms for the case where at least one of the RNA involved is of secondary structures. We then show that this algorithm might be used to deal with the practical application. We also show an approximation algorithm.

Original language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	10th Annual Symposium, CPM 99
Editors	Maxime Crochemore, Mike Paterson
Publisher	Springer Verlag
Pages	281-293
ISBN (Electronic)	9783540484523
ISBN (Print)	3540662782, 9783540662785
DOIs	https://doi.org/10.1007/3-540-48452-3_21
Publication status	Published - Jul 1999
Event	10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999) - Warwick University, Warwick, United Kingdom Duration: 22 Jul 1999 → 24 Jul 1999

Publication series

Name	Lecture Notes in Computer Science
Volume	1645
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999)
Place	United Kingdom
City	Warwick
Period	22/07/99 → 24/07/99

Access Output

10.1007/3-540-48452-3_21

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{9f27506e946d43a0a88e7f434c3f7c45,

title = "Computing Similarity between RNA Structures",

abstract = "The primary structure of a ribonucleic acid (RNA) molecule is a sequence of nucleotides (bases) over the alphabet {A,C,G,U}. The secondary or tertiary structure of an RNA is a set of base-pairs (nucleotide pairs) which forms bonds between A − U and C − G. For secondary structures, these bonds have been traditionally assumed to be one-to-one and non-crossing. This paper considers a notion of similarity between two RNA molecule structures taking into account the primary, the secondary and the tertiary structures. We show that in general this problem is NP-hard for tertiary structures. We present algorithms for the case where at least one of the RNA involved is of secondary structures. We then show that this algorithm might be used to deal with the practical application. We also show an approximation algorithm.",

author = "Kaizhong Zhang and Lusheng Wang and Bin Ma",

year = "1999",

month = jul,

doi = "10.1007/3-540-48452-3_21",

language = "English",

isbn = "3540662782",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "281--293",

editor = "Maxime Crochemore and Mike Paterson",

booktitle = "Combinatorial Pattern Matching",

address = "Germany",

note = "10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999) ; Conference date: 22-07-1999 Through 24-07-1999",

}

Zhang, K, Wang, L & Ma, B 1999, Computing Similarity between RNA Structures. in M Crochemore & M Paterson (eds), Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99. Lecture Notes in Computer Science, vol. 1645, Springer Verlag, pp. 281-293, 10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999), Warwick, United Kingdom, 22/07/99. https://doi.org/10.1007/3-540-48452-3_21

Computing Similarity between RNA Structures. / Zhang, Kaizhong; Wang, Lusheng; Ma, Bin.
Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99. ed. / Maxime Crochemore; Mike Paterson. Springer Verlag, 1999. p. 281-293 (Lecture Notes in Computer Science; Vol. 1645).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Computing Similarity between RNA Structures

AU - Zhang, Kaizhong

AU - Wang, Lusheng

AU - Ma, Bin

PY - 1999/7

Y1 - 1999/7

N2 - The primary structure of a ribonucleic acid (RNA) molecule is a sequence of nucleotides (bases) over the alphabet {A,C,G,U}. The secondary or tertiary structure of an RNA is a set of base-pairs (nucleotide pairs) which forms bonds between A − U and C − G. For secondary structures, these bonds have been traditionally assumed to be one-to-one and non-crossing. This paper considers a notion of similarity between two RNA molecule structures taking into account the primary, the secondary and the tertiary structures. We show that in general this problem is NP-hard for tertiary structures. We present algorithms for the case where at least one of the RNA involved is of secondary structures. We then show that this algorithm might be used to deal with the practical application. We also show an approximation algorithm.

AB - The primary structure of a ribonucleic acid (RNA) molecule is a sequence of nucleotides (bases) over the alphabet {A,C,G,U}. The secondary or tertiary structure of an RNA is a set of base-pairs (nucleotide pairs) which forms bonds between A − U and C − G. For secondary structures, these bonds have been traditionally assumed to be one-to-one and non-crossing. This paper considers a notion of similarity between two RNA molecule structures taking into account the primary, the secondary and the tertiary structures. We show that in general this problem is NP-hard for tertiary structures. We present algorithms for the case where at least one of the RNA involved is of secondary structures. We then show that this algorithm might be used to deal with the practical application. We also show an approximation algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84957695127&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84957695127&origin=recordpage

U2 - 10.1007/3-540-48452-3_21

DO - 10.1007/3-540-48452-3_21

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540662782

SN - 9783540662785

T3 - Lecture Notes in Computer Science

SP - 281

EP - 293

BT - Combinatorial Pattern Matching

A2 - Crochemore, Maxime

A2 - Paterson, Mike

PB - Springer Verlag

T2 - 10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999)

Y2 - 22 July 1999 through 24 July 1999

ER -

Computing Similarity between RNA Structures

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this