Another Algorithm for Computing Longest Common Increasing Subsequence for Two Random Input Sequences

摘要

We have previously developed several algorithms which deal with different input sequence scenarios respectively. In this paper, another sequential algorithm for computing Longest Common Increasing Subsequence for two random input sequences is reported. It runs in O(m n log p) time complexity and takes space of O(2(m + n + 1) p), where m and n are the length for two input sequences respectively, and p is the length of the final Longest Common Increasing Subsequence. Parallelization allows us to further reduce time and space. This algorithm has significant applications in the area of Computational Biology in manipulating the genomic sequences.