Computationally efficient cluster representation in molecular sequence megaclassification.
Molecular sequence megaclassification is a technique for automated protein sequence analysis and annotation. Implementation of the method has been limited by the need to store and randomly access a database of all the sequence pair similarities. More than 80,000 protein sequences are now present in the public databases, and the pair similarity data table for the full protein sequence database requires over 1 gigabyte of storage. In this paper we present a computationally efficient representation of groups based on a graph theory approach where sequence clusters are described by a minimal spanning tree of highest scoring similarity pairs. This representation allows a classification of N proteins to be stored in order(N) memory. The use of this minimal spanning tree representation simplifies analysis of groups, the description of group characteristics and the manual correction of artifacts resulting from false hits. The new tree representation also introduces new possibilities for artifact generation in sequence classification. Methods for detecting and removing these artifacts are discussed.
States
D J
DJ
Institute for Biomedical Computing, Washington University, St. Louis, MO 63110, USA.
Harris
N L
NL
Hunter
L
L
D000465:Algorithms; D016000:Cluster Analysis; D029968:Escherichia coli Proteins; D008432:Mathematical Computing; D011506:Proteins / Q000145:classification*; D015203:Reproducibility of Results; D012269:Ribosomal Proteins / Q000145:classification; D017421:Sequence Analysis / Q000379:methods*; D012985:Software Design
D029968:Escherichia coli Proteins; D011506:Proteins; D012269:Ribosomal Proteins; C041174:ribosomal protein L14; C043816:ribosomal protein L23, E coli