Title

New Algorithms For Finding Monad Patterns In Dna Sequences

Abstract

In this paper, we present two new algorithms for discovering monad patterns in DNA sequences. Monad patterns are of the form (l,d)- κ, where l is the length of the pattern, d is the maximum number of mismatches allowed, and κ is the minimum number of times the pattern is repeated in the given sample. The time-complexity of some of the best known algorithms to date is O(nt2ldσd), where t is the number of input sequences, n is the length of each input sequence, and σ = |∑| is the size of the alphabet. The first algorithm that we present in this paper takes O(n2t2l d/2 ) time and O(ntl d/2 σ d/2 ) space, and the second algorithm takes O(n3t3l d/2 σ d/2 ) time using O(l d/2 σ d/2 ) space. In practice, our algorithms have much better performance provided the d/l ratio is small. The second algorithm performs very well even for large values l and d as long as the d/l ratio is small. © 2004 Springer-Verlag Berlin Heidelberg.

Publication Date

12-1-2004

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

3246

Number of Pages

273-285

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-540-30213-1_40

Socpus ID

84871032737 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84871032737

This document is currently not available here.

Share

COinS