Format

Send to

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 2006 Mar;13(2):296-308.

Efficient q-gram filters for finding all epsilon-matches over a given length.

Author information

1
International NRW Graduate School in Bioinformatics and Genome Research, Center of Biotechnology, Universit├Ąt Bielefeld, Germany.

Abstract

Fast and exact comparison of large genomic sequences remains a challenging task in biosequence analysis. We consider the problem of finding all epsilon-matches between two sequences, i.e., all local alignments over a given length with an error rate of at most epsilon. We study this problem theoretically, giving an efficient q-gram filter for solving it. Two applications of the filter are also discussed, in particular genomic sequence assembly and BLAST-like sequence comparison. Our results show that the method is 25 times faster than BLAST, while not being heuristic.

PMID:
16597241
DOI:
10.1089/cmb.2006.13.296
[Indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Support Center