DASS: efficient discovery and p-value calculation of substructures in unordered data.
BACKGROUND
Pattern identification in biological sequence data is one of the main objectives of bioinformatics research. However, few methods are available for detecting patterns (substructures) in unordered datasets. Data mining algorithms mainly developed outside the realm of bioinformatics have been adapted for that purpose, but typically do not determine the statistical significance of the identified patterns. Moreover, these algorithms do not exploit the often modular structure of biological data.


RESULTS
We present the algorithm DASS (Discovery of All Significant Substructures) that first identifies all substructures in unordered data (DASS(Sub)) in a manner that is especially efficient for modular data. In addition, DASS calculates the statistical significance of the identified substructures, for sets with at most one element of each type (DASS(P(set))), or for sets with multiple occurrence of elements (DASS(P(mset))). The power and versatility of DASS is demonstrated by four examples: combinations of protein domains in multi-domain proteins, combinations of proteins in protein complexes (protein subcomplexes), combinations of transcription factor target sites in promoter regions and evolutionarily conserved protein interaction subnetworks.


BACKGROUND
The program code and additional data are available at http://www.fli-leibniz.de/tsb/DASS
Hollunder
Jens
J
Department of Theoretical Systems Biology, Leibniz Institute for Age Research--Fritz-Lipmann-Institute e. V. (former IMB Jena) Beutenbergstrasse 11, D-07745 Jena, Germany.
Friedel
Maik
M
Beyer
Andreas
A
Workman
Christopher T
CT
Wilhelm
Thomas
T
D000465:Algorithms; D029968:Escherichia coli Proteins / Q000145:classification; D020869:Gene Expression Profiling / Q000295:instrumentation* / Q000379:methods*; D008957:Models, Genetic; D015233:Models, Statistical; D010363:Pattern Recognition, Automated; D017434:Protein Structure, Tertiary / Q000235:genetics; D029701:Saccharomyces cerevisiae Proteins / Q000145:classification; D016415:Sequence Alignment / Q000295:instrumentation*; D017421:Sequence Analysis / Q000379:methods*; D014157:Transcription Factors / Q000235:genetics
D029968:Escherichia coli Proteins; D029701:Saccharomyces cerevisiae Proteins; D014157:Transcription Factors