Publication details

Brona Brejova, Daniel G. Brown, Tomas Vinar. Vector seeds: an extension to spaced seeds. Journal of Computer and System Sciences, 70(3):364-380. May 2005. Special issue on bioinformatics. Early version in WABI 2003.
Preprint, 406Kb | Download from publisher | Webpage | Early version | BibTeX | MathSciNet

Abstract

We present improved techniques for finding homologous regions in DNA and
protein sequences.  Our approach focuses on the core regions of a local
pairwise alignment; we suggest new ways to characterize these regions that
allow marked improvements in both specificity and sensitivity over existing
techniques for sequence alignment.  For any such characterization, which we
call a vector seed, we give an efficient algorithm that estimates the
specificity and sensitivity of that seed under reasonable probabilistic
models of sequence.  We also characterize the probability of a match when
an alignment is required to have multiple hits before it is detected.  Our
extensions fit well with existing approaches to sequence alignment, while
still offering substantial improvement in runtime and sensitivity,
particularly for the important problem of identifying matches between
homologous coding DNA sequences.

Photo

Contact

Mailing address:
Bronislava Brejova
Katedra informatiky
FMFI UK
Mlynska Dolina
842 48 Bratislava
Slovakia

Office: M163

Phone: +421-2-60295217

E-mail: my_surname at dcs.fmph.uniba.sk