Pattern matching in degenerate DNA/RNA sequences

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

5 Citations (Scopus)


In this paper, we consider the pattern matching problem in DNA and RNA sequences where either the pattern or the text can be degenerate i.e. contain sets of characters. We present an asymptotically faster algorithm for the above problem that works in O(n logm) time, where n and m is the length of the text and the pattern respectively. We also suggest an efficient implementation of our algorithm, which works in linear time when the pattern size is small. Finally, we also describe how our approach can be used to solve the distributed pattern matching problem.

Original languageEnglish
Title of host publicationProceedings of the 1st Workshop on Algorithms and Computation 2007, WALCOM 2007
PublisherBangladesh Academy of Sciences (BAS)
Number of pages12
Publication statusPublished - 2014
Event1st Workshop on Algorithms and Computation 2007, WALCOM 2007 - Dhaka, Bangladesh
Duration: 12 Feb 200712 Feb 2007


Conference1st Workshop on Algorithms and Computation 2007, WALCOM 2007


  • Algorithm
  • Degenerate
  • DNA/RNA sequence
  • Pattern matching


Dive into the research topics of 'Pattern matching in degenerate DNA/RNA sequences'. Together they form a unique fingerprint.

Cite this