Automated Discovery of Active Motifs in Multiple RNA Secondary Structures

Jason T.L. Wang; Bruce A. Shapiro; Dennis Shasha; Kaizhong Zhang; Chia Yo Chang

Automated Discovery of Active Motifs in Multiple RNA Secondary Structures

Jason T.L. Wang, Bruce A. Shapiro, Dennis Shasha, Kaizhong Zhang, Chia Yo Chang

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

20 Scopus citations

Abstract

In this paper we present a method for discovering approximately common motifs (also known as active motifs) in multiple RNA secondary structures. The secondary structures can be represented as ordered trees (i.e., the order among siblings matters). Motifs in these trees are connected subgraphs that can differ in both substitutions and deletions/insertions. The proposed method consists of two steps: (1) find candidate motifs in a small sample of the secondary structures; (2) search all of the secondary structures to determine how frequently these motifs occur (within the allowed approximation) in the secondary structures. To reduce the running time, we develop two optimization heuristics based on sampling and pattern matching techniques. Experimental results obtained by running these algorithms on both generated data and RNA secondary structures show the good performance of the algorithms. To demonstrate the utility of our algorithms, we discuss their applications to conducting the phylogenetic study of RNA sequences obtained from GenBank.

Original language	English (US)
Title of host publication	Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996
Editors	Evangelos Simoudis, Jiawei Han, Usama M. Fayyad
Publisher	AAAI press
Pages	70-75
Number of pages	6
ISBN (Electronic)	1577350049, 9781577350040
State	Published - 1996
Event	2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996 - Portland, United States Duration: Aug 2 1996 → Aug 4 1996

Publication series

Name	Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996

Conference

Conference	2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996
Country/Territory	United States
City	Portland
Period	8/2/96 → 8/4/96

All Science Journal Classification (ASJC) codes

Computer Science Applications
Software

Cite this

Wang, J. T. L., Shapiro, B. A., Shasha, D., Zhang, K., & Chang, C. Y. (1996). Automated Discovery of Active Motifs in Multiple RNA Secondary Structures. In E. Simoudis, J. Han, & U. M. Fayyad (Eds.), Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996 (pp. 70-75). (Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996). AAAI press.

Wang, Jason T.L. ; Shapiro, Bruce A. ; Shasha, Dennis et al. / Automated Discovery of Active Motifs in Multiple RNA Secondary Structures. Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996. editor / Evangelos Simoudis ; Jiawei Han ; Usama M. Fayyad. AAAI press, 1996. pp. 70-75 (Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996).

@inproceedings{4ec7d95011294d3780a89b4401cb29eb,

title = "Automated Discovery of Active Motifs in Multiple RNA Secondary Structures",

abstract = "In this paper we present a method for discovering approximately common motifs (also known as active motifs) in multiple RNA secondary structures. The secondary structures can be represented as ordered trees (i.e., the order among siblings matters). Motifs in these trees are connected subgraphs that can differ in both substitutions and deletions/insertions. The proposed method consists of two steps: (1) find candidate motifs in a small sample of the secondary structures; (2) search all of the secondary structures to determine how frequently these motifs occur (within the allowed approximation) in the secondary structures. To reduce the running time, we develop two optimization heuristics based on sampling and pattern matching techniques. Experimental results obtained by running these algorithms on both generated data and RNA secondary structures show the good performance of the algorithms. To demonstrate the utility of our algorithms, we discuss their applications to conducting the phylogenetic study of RNA sequences obtained from GenBank.",

author = "Wang, {Jason T.L.} and Shapiro, {Bruce A.} and Dennis Shasha and Kaizhong Zhang and Chang, {Chia Yo}",

note = "Publisher Copyright: {\textcopyright} 1996 AAAI (www.aaai.org). All Rights Reserved.; 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996 ; Conference date: 02-08-1996 Through 04-08-1996",

year = "1996",

language = "English (US)",

series = "Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996",

publisher = "AAAI press",

pages = "70--75",

editor = "Evangelos Simoudis and Jiawei Han and Fayyad, {Usama M.}",

booktitle = "Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996",

}

Wang, JTL, Shapiro, BA, Shasha, D, Zhang, K & Chang, CY 1996, Automated Discovery of Active Motifs in Multiple RNA Secondary Structures. in E Simoudis, J Han & UM Fayyad (eds), Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996. Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996, AAAI press, pp. 70-75, 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996, Portland, United States, 8/2/96.

Automated Discovery of Active Motifs in Multiple RNA Secondary Structures. / Wang, Jason T.L.; Shapiro, Bruce A.; Shasha, Dennis et al.
Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996. ed. / Evangelos Simoudis; Jiawei Han; Usama M. Fayyad. AAAI press, 1996. p. 70-75 (Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Automated Discovery of Active Motifs in Multiple RNA Secondary Structures

AU - Wang, Jason T.L.

AU - Shapiro, Bruce A.

AU - Shasha, Dennis

AU - Zhang, Kaizhong

AU - Chang, Chia Yo

PY - 1996

Y1 - 1996

N2 - In this paper we present a method for discovering approximately common motifs (also known as active motifs) in multiple RNA secondary structures. The secondary structures can be represented as ordered trees (i.e., the order among siblings matters). Motifs in these trees are connected subgraphs that can differ in both substitutions and deletions/insertions. The proposed method consists of two steps: (1) find candidate motifs in a small sample of the secondary structures; (2) search all of the secondary structures to determine how frequently these motifs occur (within the allowed approximation) in the secondary structures. To reduce the running time, we develop two optimization heuristics based on sampling and pattern matching techniques. Experimental results obtained by running these algorithms on both generated data and RNA secondary structures show the good performance of the algorithms. To demonstrate the utility of our algorithms, we discuss their applications to conducting the phylogenetic study of RNA sequences obtained from GenBank.

AB - In this paper we present a method for discovering approximately common motifs (also known as active motifs) in multiple RNA secondary structures. The secondary structures can be represented as ordered trees (i.e., the order among siblings matters). Motifs in these trees are connected subgraphs that can differ in both substitutions and deletions/insertions. The proposed method consists of two steps: (1) find candidate motifs in a small sample of the secondary structures; (2) search all of the secondary structures to determine how frequently these motifs occur (within the allowed approximation) in the secondary structures. To reduce the running time, we develop two optimization heuristics based on sampling and pattern matching techniques. Experimental results obtained by running these algorithms on both generated data and RNA secondary structures show the good performance of the algorithms. To demonstrate the utility of our algorithms, we discuss their applications to conducting the phylogenetic study of RNA sequences obtained from GenBank.

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

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

M3 - Conference contribution

AN - SCOPUS:84865929936

T3 - Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996

SP - 70

EP - 75

BT - Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996

A2 - Simoudis, Evangelos

A2 - Han, Jiawei

A2 - Fayyad, Usama M.

PB - AAAI press

T2 - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996

Y2 - 2 August 1996 through 4 August 1996

ER -

Wang JTL, Shapiro BA, Shasha D, Zhang K, Chang CY. Automated Discovery of Active Motifs in Multiple RNA Secondary Structures. In Simoudis E, Han J, Fayyad UM, editors, Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996. AAAI press. 1996. p. 70-75. (Proceedings - 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996).

Automated Discovery of Active Motifs in Multiple RNA Secondary Structures

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this