The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	A data science approach to pattern discovery in complex structures with applications in bioinformatics
Author:	Hua, Lei
View Online:	njit-etd2016-033 (xiii, 99 pages ~ 3.3 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Wang, Jason T. L. (Committee chair) McHugh, James A. (Committee member) Theodoratos, Dimitri (Committee member) Wei, Zhi (Committee member) Chen, Yi (Committee member)
Date:	2016-05
Keywords:	RNA Secondary structure Tree pattern Coaxial helical stacking Dynamic programming Pattern discovery
Availability:	Unrestricted
Abstract:	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.