A data science approach to pattern discovery in complex structures with applications in bioinformatics

Pattern discovery aims to find interesting, non-trivial, implicit, previously unknown and potentially useful patterns in data. This dissertation presents a data science approach for discovering patterns or motifs from complex structures, particularly complex RNA structures. RNA secondary and tertiary structure motifs are very important in biological molecules, which play multiple vital roles in cells. A lot of work has been done on RNA motif annotation. However, pattern discovery in RNA structure is less studied. In the first part of this dissertation, an ab initio algorithm, named DiscoverR, is introduced for pattern discovery in RNA secondary structures. This algorithm works by representing RNA secondary structures as ordered labeled trees and performs tree pattern discovery using a quadratic time dynamic programming algorithm. The algorithm is able to identify and extract the largest common substructures from two RNA molecules of different sizes, without prior knowledge of locations and topologies of these substructures. One application of DiscoverR is to locate the RNA structural elements in genomes. Experimental results show that this tool complements the currently used approaches for mining conserved structural RNAs in the human genome. DiscoverR can also be extended to find repeated regions in an RNA secondary structure. Specifically, this extended method is used to detect structural repeats in the 3'-untranslated region of a protein kinase gene.

Name thesis:degree_name

Doctor of Philosophy in Computing Sciences - (Ph.D.)

Discipline thesis:degree_discipline

Computer Science

Year

2016

Author dc:creator

• Hua, Lei

Contributors dc:contributor

• Jason T. L. Wang
• James A. McHugh
• Dimitri Theodoratos

• RNA
• Secondary structure
• Tree pattern
• Coaxial helical stacking
• Dynamic programming
• Pattern discovery
• Computer Sciences

Repository record dc:identifier

https://digitalcommons.njit.edu/dissertations/70

OAI identifier oai:identifier

oai:digitalcommons.njit.edu:dissertations-1125