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

Title:	Algorithms for pre-microrna classification and a GPU program for whole genome comparison
Author:	Zhong, Ling
View Online:	njit-etd2016-092 (x, 85 pages ~ 1.4 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Roshan, Usman W. (Committee chair) Wei, Zhi (Committee member) McHugh, James A. (Committee member) Sohn, Andrew (Committee member) Xu, Songhua (Committee member)
Date:	2016-08
Keywords:	Classification Feature mining Genome alignment Graphic processing unit CUDA Anchor
Availability:	Unrestricted
Abstract:	MicroRNAs (miRNAs) are non-coding RNAs with approximately 22 nucleotides that are derived from precursor molecules. These precursor molecules or pre-miRNAs often fold into stem-loop hairpin structures. However, a large number of sequences with pre-miRNA-like hairpin can be found in genomes. It is a challenge to distinguish the real pre-miRNAs from other hairpin sequences with similar stem-loops (referred to as pseudo pre-miRNAs). The first part of this dissertation presents a new method, called MirID, for identifying and classifying microRNA precursors. MirID is comprised of three steps. Initially, a combinatorial feature mining algorithm is developed to identify suitable feature sets. Then, the feature sets are used to train support vector machines to obtain classification models, based on which classifier ensemble is constructed. Finally, an AdaBoost algorithm is adopted to further enhance the accuracy of the classifier ensemble. Experimental results on a variety of species demonstrate the good performance of the proposed approach, and its superiority over existing methods. In the second part of this dissertation, A GPU (Graphics Processing Unit) program is developed for whole genome comparison. The goal for the research is to identify the commonalities and differences of two genomes from closely related organisms, via multiple sequencing alignments by using a seed and extend technique to choose reliable subsets of exact or near exact matches, which are called anchors. A rigorous method named Smith-Waterman search is applied for the anchor seeking, but takes days and months to map millions of bases for mammalian genome sequences. With GPU programming, which is designed to run in parallel hundreds of short functions called threads, up to 100X speed up is achieved over similar CPU executions.