Trie-Based Data Structures for Sequence Assembly

We investigate the application of trie-based data structures, suffix trees and suffix arrays in the problem of overlap detection in fragment assembly. Both data structures are theoretically and experimentally analyzed on speed and space. By using heuristics, we can greatly reduce the calls to the time-consuming dynamic programming, and have improved the speed of overlap detection up to 1,000 times with high accuracy in our collaborative DNA sequencing with Brookhaven National Laboratory. We also studied the problem of approximating maximum space savings in tries structures for unification factoring in logic programming, which is proved to be hard. 1 Introduction Trie-based data structures for strings have proven themselves in a wide variety of textsearching and biological applications. Several distinct string data structures have been developed, including suffix trees and suffix arrays, motivated by tradeoffs between construction time and space, search time, virtual memory performance..