Common substring in multiple sequences using hash based technique
Kumar Dheenadayalan, V. N. Muralidhara, Jayakrishna Katru · 2013
Searching for the longest common substring in multiple sequences is of great practical application in the field of Bioinformatics. Two memory efficient solutions to the problem of finding common substrings in multiple sequences are proposed in this paper. First algorithm is a combination of hashing technique and Suffix Tree to find common substrings in long DNA or Protein sequences. This algorithm is three times more memory efficient when compared to other alternate data structures. k-Truncated Suffix Tree, a variation of Suffix Tree was proposed recently to find common substrings for short sequences. The second algorithm uses hashing with separate chaining for short sequences which offers a memory advantage of around 10 times when compared to k-truncated Suffix Tree. These algorithms also offer a great potential for parallelization of the search process which can improve the run time of the search by a large factor.