English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

The generalised k-Truncated Suffix Tree for time- and space-efficient searches in multiple DNA or protein sequences

MPS-Authors

Schulz,  Marcel H.
Max Planck Society;

/persons/resource/persons50496

Robinson,  Peter N.
Research Group Development & Disease (Head: Stefan Mundlos), Max Planck Institute for Molecular Genetics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Schulz, M. H., Bauer, S., & Robinson, P. N. (2008). The generalised k-Truncated Suffix Tree for time- and space-efficient searches in multiple DNA or protein sequences. International Journal of Bioinformatics Research and Applications: Ijbra, 4(1), 81-95. doi:10.1504/IJBRA.2008.017165.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-80B3-8
Abstract
Efficient searching for specific subsequences in a set of longer sequences is an important component of many bioinformatics algorithms. Generalised suffix trees and suffix arrays allow searches for a pattern of length n in time proportional to n independent of the length of the sequences, and are thus attractive for a variety of applications. Here, we present an algorithm termed the generalised k-Truncated Suffix Tree (kTST), that represents an adaption of Ukkonen's linear-time suffix tree construction algorithm. The kTST algorithm creates a k-deep tree in linear time that allows rapid searches for short patterns of length of up to k characters. The kTST can offer advantages in computational time and memory usage for searches for short sequences in DNA or protein sequences compared to other suffix-based algorithms.