Project

• Title: Design a "generalized suffix tree" C++ class. Design an algorithm/program to find the maximal unique matches between two long strings (ideally chromosomes).
• Time slot: March 15th, 2016 (2:00pm - 2:30pm)

Progress

• Read the description of the generalized suffix tree in Gusfield's book.
• Read about the Ukkonen's algorithm which constructs the suffix trees in linear time.
• Implemented Ukkonen's Algorithm in C++ and tested it for smaller strings.
• Implemented logic to identify the Maximum Unique Matches.
• Currently testing the code on longer strings and looking for ways to make it memory efficient.

References

• Linear-Time Construction of Suffix Trees from Algorithms on Strings, Trees, and Sequences, Dan Gusfield
• Here is a video which explains the Ukkonen's Algorithm with examples.
• Ukkonen's Algorithm explained in plain english also gives tips on how to implement it. (Link for the implementation has been given below)
• Here is the implementation given on the link. (Never tried running it directly but it gives the structure)