Title

Pruner: Algorithms For Finding Monad Patterns In Dna Sequences

Abstract

We present new algorithms for discovering monad patterns in DNA sequences. Monad patterns are of the form (l,d)-k, where l is the length of the pattern, d is the maximum number of mismatches allowed, and k 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(nt 2l d/∑/ d), where t is the number of input sequences, and n is the length of each input sequence. The first algorithm that we present takes O(n 2t 2l d/2/∑/ d/22) and space O(ntl d/2/∑/ d/2), and the second algorithm takes O(n 3t 3 l 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. Pattern discovery, regulatory patterns, k-mismatch patterns.

Publication Date

12-1-2004

Publication Title

Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

Number of Pages

662-665

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

14044251521 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS