Introduction: The surprising presence of P. vivax in West Africa and their ability to infect a Duffy negative population is one more threat to public health. In order to contribute to malaria elimination efforts, there is a need to investigate the origin and characteristics of P. vivax population isolates in Northern Mali. Next Generation Sequence Analysis (NGSA) can help us understand parasite genetic characteristics although low parasite density is a challenge for whole genome sequencing (WGS). In the present work, we investigated if selective whole genome amplification (sWGA) can enrich P. vivax DNA extracted from Rapid Diagnostic Tests (RDTs) for Whole Genome Sequencing. We also investigated the origin and the susceptibility to antimalarial drugs of the strains isolated in Northern Mali. Methods: Parasite DNA was extracted from 267 RDTs using the QIAamp DNA mini kit, then nested PCR and 7 samples were positive for P. vivax. After sWGA, the whole genomes were sequenced using the Illumina platform. Next Generation Sequences Analysis was done followed by population differentiation analyses. Twenty-two additional P. vivax whole genomes from other parts of the World were downloaded from the European Nucleotide Archive for further Neighbour Joining analysis. Results: The sequences extracted from RDTs showed high contamination with human DNA (80%). From the parasite DNA, in total 69529 SNPs were found in the seven P. vivax strains of Northern Mali. The most significant p-values per SNP were carried by the chromosomes 2, 3, 4, 5, 12, 13 and 14. With regard to variant effects, the Transition/Transversion ratio was 1.1. The density of variants with a high effect was 1.62%. There was no mutation associated with antimalarial drugs resistance on pvcrt-o or pvmdr-1 genes. Pairwise differentiation suggests a high degree of relatedness between P. vivax strains isolated in Northern Mali. The NeighboursJoining analysis shows clearly that strains from Mali cluster together and are genetically distinct from those from Mauritania, which shares a border with Mali. The strains isolated in Northern Mali are genetically closer to those from Madagascar, India and Latina America. Conclusion: We did not identify mutations associated to the resistance to antimalarial drugs in pvcrt-o and pvmdr-1 genes. This study confirms that P. vivax strains genetically distinct from those of Mauritania are circulating in Mali. Finally, we conclude that sWGA is a feasible approach for P. vivax DNA enrichment for WGS despite the high proportion of human contamination.

High-throughput next-generation sequencing techniques have hugely decreased the cost and increased the speed of sequencing, resulting in an explosion of sequencing data. This motivates the development of high-efficiency sequence alignment algorithms. In this thesis, I present multiple bit-parallel and Single Instruction Multiple Data (SIMD) algorithms that greatly accelerate the processing of biological sequences. The first chapter describes the BitPAl bit-parallel algorithms for global alignment with general integer scoring, which assigns integer weights for match, mismatch, and insertion/deletion. The bit-parallel approach represents individual cells in an alignment scoring matrix as bits in computer words and emulates the calculation of scores by a series of logic operations. Bit-parallelism has previously been applied to other pattern matching problems, producing fast algorithms. In timed tests, we show that BitPAl runs 7 - 25 times faster than a standard iterative algorithm. The second part involves two approaches to alignment with substitution scoring, which assigns a potentially different substitution weight to every pair of alphabet characters, better representing the relative rates of different mutations. The first approach extends the existing BitPAl method. The second approach is a new SIMD algorithm that uses partial sums of adjacent score differences. I present a simple partial sum method as well as one that uses parallel scan for additional acceleration. Results demonstrate that these algorithms are significantly faster than existing SIMD dynamic programming algorithms. Finally, I describe two extensions to the partial sums algorithm. The first adds support for affine gap penalty scoring. Affine gap scoring represents the biological likelihood that it is more likely for gaps to be continuous than to be distributed throughout a region by introducing a gap opening penalty and a gap extension penalty. The second extension is an algorithm that uses the partial sums method to calculate the tandem alignment of a pattern against a text sequence using a single pattern copy. Next generation sequencing data provides a wealth of information to researchers. Extracting that information in a timely manner increases the utility and practicality of sequence analysis algorithms. This thesis presents a family of algorithms which provide alignment scores in less time than previous algorithms.