DNA Sequence Pattern Match/ String Search Problem

Question: The DNA double helix consists of a long strand of four bases: adenine (abbreviated A), cytosine (C), guanine (G) and thymine (T). Thus, it can be represented as a long string containing the characters A, C, G, and T. The field of bio-informatics involves storing and searching of DNA sequence data. What is a good data structure to facilitate storage and string match/search operation on this kind of data? Write a class that stores the DNA sequence and implement a method which takes another DNA sub-sequence and returns the position of this sub-sequence in the first DNA sequence.

Solution: There are several linear time string matching algorithms. See http://en.wikipedia.org/wiki/String_searching_algorithm for a list of such algorithms.
Often a data structure called Suffix Tree or PAT tree is used in DNA sequencing applications in the field of Bio-informatics. A Suffix tree data structure facilitates string match/search in O(m) complexity, where m is the length of the sub-string. It takes an initial O(n) time required to build the suffix tree.
One concern with suffix tree is the high amount of space/memory needed. But, with a small alphabet ( only 4 characters in the DNA search problem ) , its not too bad. More over, there are some advanced techniques that can be used to further reduce the storage requirements.
A thorough treatment of suffix trees can be found here.
I still have some bugs in my class implementation, so I will post the code in the next couple of days.

Linked List: Merged List Problem

Problem: There are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join.

Solution 1:

1. Find length of both linked lists, say len1 and len2.
2. Make current pointers for both lists equidistant from the common node. If one of the lists is longer we need to advance its current pointer by len1 - len2 (assuming list1 is longer). Now both current pointers should be equidistant from the common node. If both lists are same len, do nothing in step 2.
3. Traverse both lists simultaneously while comparing the current pointers for equality. At ant point if they are equal we have found the first common node. If we reach the end of the lists without find the common node then the lists do not overlap.

Solution 2 : This solution only tells if the lists are joined, not where though. Interesting technique nevertheless.

1. Update the tail of one of the lists to point to the head of the other.
2. Now use the linked list cycle/loop detection technique to find if there is a loop in the combined list.
3. If there is a loop then the list have node(s) in common, otherwise they don't.