Introduction To LCA

Description

Lowest Common Ancestor -- fast preprocessing of the suffix tree for constant-time lowest common ancestor queries is needed in order to achieve optimal suffix preprocessing/querying algorithm. We will review the LCA algorithm given by Bender and Farach-Colton, "The LCA Problem Revisited." LATIN, pages 88-94, 2000 in class. Compare the performance of their LCA preprocessing and query operations to that of the algorithm proposed by Schieber and Vishkin, "On finding lowest common ancestors: simplification and parallelization", SIAM Journal on Computing, Volume 17, Issue 6 (December 1988). the algorithm is presented in chapter 8 of Gusfield, "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology".

Lowest common ancestor

Definition: The deepest node in a tree that is an ancestor of two given leaves

Now we come to know that what is basically LCA and what we are trying to do, Let me explain you in a little more detail what is lowest common ancestor and what we are trying to do in this project. For example 1 is the root node and 2 and 3 are its child, so now question is that what the LCA of 2 and 3, answer is is 1. Let say 1 is the child of some other node in this case LCA of 2 and 3 will be the same. But what is the LCA of 2 and the new node (the ancestor of 1), now the LCA will be the ancestor of 1.

Now we will probably think why we are wasting our time to find LCA and why we are coding a huge project? Interesting question! The answer is pretty straight forward and complicated too. As we will learn in our upper division courses that how to find text and what is Suffix Tree, and how biologist use these types of techniques for genes pattern matching. I will put some useful references about Suffix Tree and biotechnical algorithm

As we already know what LCA is, let’s talk about two different algorithms and discuss which one is more better by finding the run time comparison.

Website Maintained By Muhammad Ahsan Yusuf ©.All Rights Reserved