MSc Thesis - The birectional BWT and its applications

Topic

TODO

Journal

• 2014-09-15: I read up on templates, forked the official seqan repository, set Eclipse up and got my first app running
• 2014-09-17: Writing an app using FMIndex and reading into the code for FMIndex and TopDown-Iterators
• 2014-09-19: Continued reading into the code and started coding the skeleton for Bidirectional-Index
• 2014-09-20: Continued coding the skeleton for Bidirectional-Index
• 2014-09-21: Tried some different design ideas. Insight: none of them fits in smoothly. Will be asking David for feedback tomorrow
• 2014-09-23: I decided to stick on the original design idea and continued, but couldn't build the code
• 2014-09-25: Writing down the disadvantages of the current design I haven't seen before and sending David an e-mail with some questions and notes.
• 2014-09-25: Writing down the disadvantages of the current design I haven't seen before and sending David an e-mail with some questions and notes.
• 2014-09-29: Brushing up on BWT, coding BWT and backward-search in Haskell, testing (just for fun and to make sure that I fully understand the algorithm)
• 2014-09-30: Reading the paper about bidirectional BWT and coding it in Haskell (just for fun and to avoid debugging logical errors in C++ )
• 2014-10-01: Debugging the skeleton
• 2014-10-03: Debugging the skeleton - it finally works! I missed the wrapper for Iter<...> and the "Type"-definition
• 2014-10-05: Modifying the iterator such that all the methods that work on FMIndex-Iter also work on BiFMIndex-Iter without writing dozens of wrapper-Methods. I specialized only some methods. goDown(BiFM-Index-Iter) still throws a Segfault.
• 2014-10-06: Narrowed down the cause for the segfault.
• 2014-10-07: Reason for segfault identified: letting the Iterator for BidirectionalFMIndex inherit from the Iterator for FMIndex doesn't work without wrapping a lot of functions. If BidirectionalFMIndex-Iter is castet to FMIndex-Iterator in container(), the pointers change. I'll have to choose another way/design.
• 2014-10-11: Implementing the iterator as two iterators (as proposed by David in the beginning. Still not satisfied with the design idea, but I finally want to code the bidirectional-BWT to have some working code and knowing that I've done more than just try&error)
• 2014-10-13: implemented left-extionsion of strings and maintaining both SA-ranges
• 2014-10-15: implemented right-extionsion of strings and maintaining both SA-ranges & testing
• 2014-10-21: past days: implemented wrapper, continued testing, cleaned up the code, etc.
• --- Holiday, midterms, getting feedback ---
• 2014-11-15: Removing the BiDirectional-struct from the 2nd template argument and introduced subclassing for the 1st template argument (FMIndex). Not working at all so far
• 2014-11-16: Moving code into seperate header files, finishing some TODOs

References

• Github fork: https://github.com/cpockrandt/seqan