Finding variations between two genomes can be approached using de novo assembly with colored de Bruijn graphs [1]. With uncompressed colored / coverage annotated de Bruijn graph, such approach suffers from requiring enermous amount of RAM. However, there exist a succinct representation for de Bruijn graphs [2]. The goal of the project is to implement the succinct de Bruijn graph and explore ways to compress colored / coverage annotated de Bruijn graphs on real read data sets, to enable more space-efficient approach for De novo assembly -based variant calling.

[1] Z. Iqbal, M. Caccamo, I. Turner, P. Flicek, G. McVean. De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat Genet. 2012 Jan 8;44(2):226-32. doi: 10.1038/ng.1028.

[2] A. Bowe, T. Onodera, K. Sadakane, and T. Shibuya. Succinct de Bruijn Graphs. In Proc. WABI 2012. Springer, LNCS 7534, pp. 225-235, 2012.