Alan Kuhnle

Area of research

Computational Theory and Mathematics · Artificial Intelligence

Research interest

Research topics from publications: Efficient Construction of a Complete Index for Pan-Genomics Read Alignment; Succinct dynamic de Bruijn graphs; Influence Diffusion in Online Social Networks With Propagation Rate Changes; Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization; DASH: A Distributed and Parallelizable Algorithm for Size-Constrained Submodular Maximization; Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time; Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel. Representative work: Short-read aligners predominantly use the FM-index, which is easily able to index one or a few human genomes. However, it does not scale well to indexing collections of thousands of genomes. Driving this issue are the two chief components of the index: (1) a rank data structure over the Burrows-Wheeler Transform (BWT) of the string that will allow us to find the interval in the string's suffix array (SA), and (2) a sample of the SA that - when used with the rank data structure - allows us to access the SA. The rank data structure can be kept small even for large genomic databases, by run-length compressing the BWT, but until recently there was no means known to keep the SA sample small witho MOTIVATION: The de Bruijn graph is one of the fundamental data structures for analysis of high throughput sequencing data. In order to be applicable to population-scale studies, it is essential to build and store the graph in a space- and time-efficient manner. In addition, due to the ever-changing nature of population studies, it has become essential to update the graph after construction, e.g. add and remove nodes and edges. Although there has been substantial effort on making the construction and storage of the graph efficient, there is a limited amount of work in building the graph in an efficient and mutable manner. Hence, most space efficient data structures require complete reconstruc