A time efficient algorithm for finding longest common subsequence from two molecular sequences


Conference Paper

This paper presents a new algorithm for finding Longest Common Subsequence from two given sequences of DNA, Proteins etc of interest. We have presented a Sequential Algorithm, which is quite effective. Our method compares the given Database sequence of DNA representing the entire/partial genetic structure of some organism (such sequences are very long), which is assumed to be stored in the database only once with a given query sequence. Although our method can be applied for Protein or RNA Sequences but here we have only taken DNA Sequences. The bucket sorting method where elements are collected in buckets and then collected in some manner to get the sorted list inspires our algorithm. Our algorithm collects the index positions of the database sequence in respective buckets which becomes the input for the main algorithm. Given algorithm is quite effective as far as time complexity is concerned. © 2007 IEEE.

Full Text

Duke Authors

Cited Authors

  • Rizvi, SAM; Agarwal, P

Published Date

  • December 1, 2007

Published In

Start / End Page

  • 302 - 306

International Standard Serial Number (ISSN)

  • 1071-121X

International Standard Book Number 10 (ISBN-10)

  • 1424410339

International Standard Book Number 13 (ISBN-13)

  • 9781424410330

Digital Object Identifier (DOI)

  • 10.1109/NEBC.2007.4413398

Citation Source

  • Scopus