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.

Tree: Find Lowest Common Ancestor

Problem: Given a binary search tree and 2 values find the lowest common ancestor.

Solution: Lets take a sample tree and see what finding the lowest ancestor means. The figure to the left shows the sample tree. To take an example, lets say the problem asked us to find the lowest common ancestor for nodes 10 and 14. Visually we can tell that node 12 is the lowest common ancestor. 15 is also a common ancestor but its not the lowest.

Since the tree is a binary search tree all the nodes to the right of any node within the tree have greater values that the node itself and all the nodes to the left have smaller values than the node. This property helps us in implementing the optimal solution to this problem. We start analyzing values at the root node and recursively arrive at a node where the two input values fall on different sides of the node. If they are on the same side of the node we recursively analyze the corresponding branch. For example, we start at 15 and see that 10 and 14 are both less than 15, so we choose the left branch and arrive at 12. Now, 10 is on the left of 12 and 14 is on the right. This is the node we are interested in. There is a non-recursive solution to this problem which basically uses the same idea, which I'll post soon.

Code:

Node * Find-Lowest-Common-Ancestor(Node *pRoot, int val1, int val2)
{
 if(pRoot == NULL) return NULL;

 // if both the values are less than the current node value
 // the common ancestor must be to the left
 if(val1 < pRoot->data && val2 < pRoot->data);
 {
    return Find-Lowest-Common-Ancestor(pRoot->left, val1, val2);
 }
 // if both the values are greater than the current node value
 // the common ancestor must be to the right
 else if(val1 > pRoot->data && val2 > pRoot->data)
 {
    return Find-Lowest-Common-Ancestor(pRoot->right, val1, val2);
 }
 else
 {
    return pRoot;
 }
}

Tree: PreOrder Traversal without Recursion

Problem: Write the code for pre-order traversal of a binary tree without recursion.

Solution: Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees without using recursion. This can sometimes make the problem challenging. In this problem, even though we will not use recursion explicitly, we will use the Stack data structure that emulates what recursion does.

Code:

typedef struct _node
{
   int data;
   struct _node * left;
   struct _node * right;
} Node;

void Pre-Order-Traversal-Non-Recursive(Node * root)
{
   Stack nodeStack;
   nodeStack.Push(root);
   
   // while stack is not empty
   while(nodeStack.Count > 0)
   {
      Node * currentNode = nodeStack.Pop();
      printf("%d\n", currentNode->data);
      nodeStack.Push(currentNode->right);
      nodeStack.Push(currentNode->left);
   }
}

Note: This implementation, even though avoids recursion, does not take any less memory compared to the recursive method since we are using an external stack to emulate recursion.

Tree: Traversal (PreOrder, InOrder, PostOrder)

Problem: What are the different ways of traversing a non-empty Tree?

Solution: Tree traversal can be divided into 2 major methods. First is Depth-First-Traversal and the second is Breadth-First-Traversal.

Depth-First-Traversal(DFT or DFS): The idea is to recursively keep visiting the nodes in the left branch. When all nodes are visited in the left branch, visit the right branch recursively and move backup. Think of each branch(left or right) as a sub-tree.

Breadth-First-Traversal(BFT or BFS): Here all the nodes at the same level are visited before visiting nodes at a lower level. See the post on Breadth First Tree Traversal for an implementation using a Queue.

There are 3 different ways of Depth-First-Traversal depending on when the root node is visited with respect to the children sub-trees.

1. Pre-Order Traversal: The root node is visited before visiting the children nodes/sub-trees.

Algorithm:
a. Visit root node
b. Recursively visit left sub-tree
c. Recursively visit right sub-tree


Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    printf("%d", node->data);
    PreOrderTraversal(node->left);
    PreOrderTraversal(node->right);
}

2. In-Order Traversal: The root node is visited before visiting the right sub-tree but after visiting the left sub-tree.

Algorithm:
a. Recursively visit left sub-tree
b. Visit root node
c. Recursively visit right sub-tree


Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    PreOrderTraversal(node->left);
    printf("%d", node->data);
    PreOrderTraversal(node->right);
}

3. Post-Order Traversal: The root node is visited after visiting the left sub-tree as well as the right sub-tree.

Algorithm:
a. Recursively visit left sub-tree
b. Recursively visit right sub-tree
c. Visit root node
Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    PreOrderTraversal(node->left);
    PreOrderTraversal(node->right);
    printf("%d", node->data);
}

Tree: Breadth First Search

Problem: Write code for doing a breadth first search in a Tree data structure.

Solution: Breadth first search inspects items one level at a time starting with the root node. This is unlike the Depth First Search where the nodes in the left most branch are visited until there are no more nodes and then backtracks.

The problem with implementing a breadth first search is that we have to remember the list of nodes at the same level before moving to the next level. This can be achieved by using a queue data structure. See this post on details of how to implement a Queue using an array. Every time we visit a node, we inspect the data contained in the node before Enqueueing both children to the Queue. If the node contains the data we were searching for we return the pointer to that node.

//Breadth First Search (BFS) method searches the tree one level at a time

Node * Breadth-First-Search(Node *root, int searchValue)
{
    Queue queue;
    queue.Enqueue(root);
    Node * currentNode;
    while(currentNode = queue.Dequeue())
    {
       if(currentNode->data == searchVal)
           return currentNode;

       queue.Enqueue(currentNode->left);
       queue.Enqueue(currentNode->right);
    }
}