Development of rapid, sensitive sequence alignment tools for application to high-throughput sequencing data

Abstract

This thesis explores methods in two topics related to biological sequence analysis: the mapping of high-throughput sequencing (HTS) reads to a reference sequence, and multiple sequence alignment. Three novel computational tools are presented and evaluated as products of these explorations. The first of these tools, RAMICS, is a reference mapper designed to align HTS reads sequenced from coding DNA to a short reference sequence « lOOOObp). RAMICS uses a biologically realistic hidden Markov model to map HTS reads in codon space, while simultaneously accounting for platform-specific sequencing errors. This approach means that RAMICS is substantially more accurate than popular reference mapping tools when mapping coding DNA containing sequencing errors, while maintaining competitive speed performance through the use of graphics processing units (GPUs). RAMICS is successfully applied to the challenging problem of mapping HTS reads sequenced from one human immunodeficiency virus (HIV) subtype to a reference sequence from another subtype. AFAB, the second tool developed in this thesis, is a flexible reference mapping benchmark. AFAB is novel in that it is capable of including both sequencing errors and biological diversity from the reference sequence in the appraisal of sequence mapping tools. AFAB tests not only the coverage obtained by a mapping tool and the percentage of reads mapped correctly, but also the accuracy of consensus SNP calls. AFAB simulates HTS reads from the second sequence of a user-provided pairwise alignment, and can then be used to test any mapping tool on its ability to correctly map these reads to the first sequence in the alignment, reconstructing the relationship between the two sequences. Any pairwise alignment can be used as input and this thesis presents use cases that explore reference mapping between HN subtypes, mapping for metagenomics analysis of hepatitis C virus (HCy) and related species, and reference mapping between closely related eukaryotic species.