Geometric interpretation of biological data: algorithmic solutions for next generation sequencing analysis at massive scale

2015-03-30Recent advances in high-throughput sequencing technologies have provided scientists with unprecedented abilities to unravel the secrets of nature. Substantial cost reduction in such technologies has eliminated a major bottleneck in biological studies and led to initiation of projects that generate terabytes of data. This phenomenon demands novel algorithmic solutions to deal with massive amount of data. Unfortunately, most of the existing algorithms suffer from scalability issues and their performance is negatively affected as data size grows. ❧ This dissertation is focused on structuring biological data at massive scale. Alignment-free representations are used in this work due to their computational advantages. Such representations are transformed to a geometric context enabling new interpretations of the problems and introducing a novel set of techniques to organize, handle and compare sequence data very efficiently. This approach is employed to study two different scenarios: (1) in local alignment-free sequence comparison, a pair of sequences are searched for the most similar fixed-length fragments. (2) In next generation sequencing data, numerous samples resulting from sequencing experiments are given and the goal is to build a content-based database engine such that new data could be rapidly queried for similar existing samples. To cope with the computational requirements, no downstream analysis such as mapping or assembly is undertaken. ❧ Several examples are presented to demonstrate the ability of the designed data structures to address problems under both scenarios. Particular attention is paid to the latter due to the importance of having a rapid data retrieval framework for the next generation sequencing technologies. With the flexibility in representation and achieved scalability in indexing scheme of the database engine, actionable inferences and recommendations can be drawn in seconds for a variety of heterogeneous biological data types