Search Results (1 - 2 of 2 Results)

Sort By  
Sort Dir
Results per page  

Abu Doleh, AnasHigh Performance and Scalable Matching and Assembly of Biological Sequences
Doctor of Philosophy, The Ohio State University, 2016, Electrical and Computer Engineering
Next Generation Sequencing (NGS), the massive parallel and low-cost sequencing technology, is able to generate an enormous size of sequencing data. This facilitates the discovery of new genomic sequences and expands the biological and medical research. However, these big advancements in this technology also bring big computational challenges. In almost all NGS analysis pipelines, the most crucial and computationally intensive tasks are sequence similarity searching and de novo genome assembly. Thus, in this work, we introduced novel and efficient techniques to utilize the advancements in the High Performance Computing hardware and data computing platforms in order to accelerate these tasks while producing high quality results. For the sequence similarity search, we have studied utilizing the massively multithreaded architectures, such as Graphical Processing Unit (GPU), in accelerating and solving two important problems: reads mapping and maximal exact matching. Firstly, we introduced a new mapping tool, Masher, which processes long~(and short) reads efficiently and accurately. Masher employs a novel indexing technique that produces an index for huge genome, such as the human genome, with a small memory footprint such that it could be stored and efficiently accessed in a restricted-memory device such as a GPU. The results show that Masher is faster than state-of-the-art tools and obtains a good accuracy and sensitivity on sequencing data with various characteristics. Secondly, maximal exact matching problem has been studied because of its importance in detection and evaluating the similarity between sequences. We introduced a novel tool, GPUMEM, which efficiently utilizes GPU in building a lightweight indexing and finding maximal exact matches inside two genome sequences. The index construction is so fast that even by including its time, GPUMEM is faster in practice than state-of-the-art tools that use a pre-built index. De novo genome assembly is a crucial step in NGS analysis because of the novelty of discovered sequences. Firstly, we have studied parallelizing the de Bruijn graph based de novo genome assembly on distributed memory systems using Spark framework and GraphX API. We proposed a new tool, Spaler, which assembles short reads efficiently and accurately. Spaler starts with the de Bruijn graph construction. Then, it applies an iterative graph reduction and simplification techniques to generate contigs. After that, Spaler uses the reads mapping information to produce scaffolds. Spaler employs smart parallelism level tuning technique to improve the performance in each of these steps independently. The experiments show promising results in term of scalability, execution time and quality. Secondly, we addressed the problem of de novo metagenomics assembly. Spaler may not properly assemble the sequenced data extracted from environmental samples. This is because of the complexity and diversity of the living microbial communities. Thus, we introduced meta-Spaler, an extension of Spaler, to handle metagenomics dataset. meta-Spaler partitions the reads based on their expected coverage and applies an iterative assembly. The results show an improving in the assembly quality of meta-Spaler in comparison to the assembly of Spaler.


Umit Catalyurek (Advisor); Kun Huang (Committee Member); Fusun Ozguner (Committee Member)


Bioinformatics; Computer Engineering


bioinformatics;sequence similarity;indexing;graphical processing unit;Apache Spark;de Bruijn graph;de novo assembly;metagenomics

Ozturk, OzgurFeature extraction and similarity-based analysis for proteome and genome databases
Doctor of Philosophy, The Ohio State University, 2007, Computer and Information Science
Bioinformatics will boost our understanding of how life works and enhance medicinal and bio technology. Very large amounts of data is being produced by the experiments of the researchers trying to decipher the complexity of life. In this dissertation, I present our methods for search and analysis of microbiological sequence and 3D protein structure data. We developed methods to map genomic and proteomic sequencesinto metric feature vector spaces in order to facilitate the building of index structures that have practical, accurate, and sensitive filtering capabilities. Similarity distance functions between these N-gram frequency vectors and N-gram wavelet vectors are defined such that these distances satisfy desired properties to represent the original distance between the subsequences corresponding to the vectors. These vectors are indexed using a compressed, multiresolution, grid style data structure for efficient pruning of the candidates in the search space. Our method to index protein structuresdefines and utilizes spatial profiles, i.e., summaries constructed from the geometrical and biochemical properties that characterize the neighborhood around the geometrically significant sites of proteins. These features are then scored using a statistical measure, for their ability to distinguish a family of proteins from a background set of unrelated proteins, and successful features are combined into a representative set for the protein family. Unlike most of the currently available methods, our methods are able to capture structurally local motifs. The results verify that our method is successful both in identifying the distinctive sites of a given family of proteins, and in classifying proteins using the extracted features. These tools utilize accurate and compact representations of data together with better similarity measures, new data structures and algorithms, and apply data mining techniques in novel ways to help researchers extract information from very large data repositories and make better use of them.


Hakan Ferhatosmanoglu (Advisor)


; Bioinformatics; Structural Motifs; Sequence Indexing; Sequence Similarity; Subsequence Similarity; Substructure Similarity; Very Large Databases; Similarity Search; k-NN Search; Range Search; Approximate Querying; Quantized Index; Multiresolution Search