Executive Summary : | Over the past half-decade, high-throughput human sequencing data analyses have primarily used a single reference genome, such as a single string, obtained from a few individuals. However, with the discovery of genomic variations in the human population, research has turned to replacing a single reference genome with a pangenome representation that encodes all such variation. A common representation is a labeled graph. As more variations become available, pangenome graphs and their data structures need to be enriched. In bioinformatics, processing the genome graph to develop data structures that efficiently report properties for error correction, sequencing, and alignment are essential. Dynamic graph algorithms, which maintain data structures or properties for graphs that undergo updates, are used to maintain these structures. These algorithms deal with updates in the form of insertion or deletion of edges or vertices. For bioinformatics applications, the most interesting model of dynamic graph algorithms is one that allows new genome variations to be added to the pangenome. However, the applications of existing dynamic graph algorithms in bioinformatics have been limited, despite significant progress in dynamic string data structures. This project aims to develop dynamic graph algorithms for key problems relevant to pangenome graphs and implement and test them on real human pangenome data. The goal is to contribute to these problems in theoretical aspects by developing algorithms with better time and space guarantees, and study these problems in practical empirical aspects to improve time and space performance on real data. |