3 ms·
I'm most definitely not an expert in this area, but I have recently taken interest in learning about "succinct data structures", which from what I understand ha
by denvaar 4y ago
I'm most definitely not an expert in this area, but I have recently taken interest in learning about "succinct data structures", which from what I understand have their place in bioinformatics.
It's been a challenging topic to learn about, because most of the information comes from Computer Science papers and articles where the information is presented in a very formal, mathematical way, which I am just not used to.
Normally when thinking about data structures and algorithms, we're mostly concerned with optimizing for speed. Space complexity is not usually as big of a consideration. Succinct data structures are all about creating ways to achieve good runtime performance while representing the data in a "compressed" format. I think this comes in handy when doing things like DNA sequencing since data sets are so large.
I'm excited to check out some of links in the post, and in case any one else is interested in learning more about succinct data structures, here's a few resources I'd recommend:
Prof. Ben Langmead's YouTube channel: https://www.youtube.com/user/BenLangmead/featured https://www.youtube.com/user/BenLangmead/featured
Alex Bowe's blog has some good content: https://www.alexbowe.com/articles/ https://www.alexbowe.com/articles/
Prof. Erik Demaine's "succinct" lectures from his adv. data structures course at MIT on YouTube: https://www.youtube.com/watch?v=3Y2weLDiUWw https://www.youtube.com/watch?v=3Y2weLDiUWw
Edward Kmett's Haskell live coding session going into some details about succinct: https://www.youtube.com/watch?v=9MKEmNNJgFc https://www.youtube.com/watch?v=9MKEmNNJgFc
There's also a lot of research papers, which you should be able to find by searching for "succinct data structures" (Jacobson, Munro, Brodnik, Raman, Rao, Navaro, Sadakane just to name a few). I at least have a basic CS undergraduate degree, but many of these papers are over my head, but I have still been able to slowly understand more and more. Some I had to purchase.