title: The generalised k-Truncated Suffix Tree for time-and space-efficient searches in multiple DNA or protein sequences.
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.
authors.affiliation: Institute fur Medizinische Genetik, Charite Universitatsmedizin Berlin, Augustenburger Platz 1, 13353 Berlin, Germany.marcel.schulz@molgen.mpg.de
authors.forename: Marcel H
authors.initials: MH
authors.lastname: Schulz
authors.forename: Sebastian
authors.initials: S
authors.lastname: Bauer
authors.forename: Peter N
authors.initials: PN
authors.lastname: Robinson
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*