title: Massive fungal biodiversity data re-annotation with multi-level clustering.
abstract: With the availability of newer and cheaper sequencing methods, genomic data are being generated at an increasingly fast pace. In spite of the high degree of complexity of currently available search routines, the massive number of sequences available virtually prohibits quick and correct identification of large groups of sequences sharing common traits. Hence, there is a need for clustering tools for automatic knowledge extraction enabling the curation of large-scale databases. Current sophisticated approaches on sequence clustering are based on pairwise similarity matrices. This is impractical for databases of hundreds of thousands of sequences as such a similarity matrix alone would exceed the available memory. In this paper, a new approach called MultiLevel Clustering (MLC) is proposed which avoids a majority of sequence comparisons, and therefore, significantly reduces the total runtime for clustering. An implementation of the algorithm allowed clustering of all 344,239 ITS (Internal Transcribed Spacer) fungal sequences from GenBank utilizing only a normal desktop computer within 22 CPU-hours whereas the greedy clustering method took up to 242 CPU-hours.
authors.affiliation: Bioinformatics group, CBS-KNAW Fungal Biodiversity Centre, Utrecht, The Netherlands.
authors.forename: Duong
authors.initials: D
authors.lastname: Vu
authors.affiliation: Bioinformatics group, CBS-KNAW Fungal Biodiversity Centre, Utrecht, The Netherlands.
authors.forename: Szániszló
authors.initials: S
authors.lastname: Szöke
authors.affiliation: Computational Systems Biology, Max Planck Institute for Informatics, Saarbrücken, Germany.
authors.forename: Christian
authors.initials: C
authors.lastname: Wiwie
authors.affiliation: Institute for Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark.
authors.forename: Jan
authors.initials: J
authors.lastname: Baumbach
authors.affiliation: University of Perugia, Perugia, Italy.
authors.forename: Gianluigi
authors.initials: G
authors.lastname: Cardinali
authors.affiliation: 1] Computational Systems Biology, Max Planck Institute for Informatics, Saarbrücken, Germany [2] Institute for Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark.
authors.forename: Richard
authors.initials: R
authors.lastname: Röttger
authors.affiliation: Bioinformatics group, CBS-KNAW Fungal Biodiversity Centre, Utrecht, The Netherlands.
authors.forename: Vincent
authors.initials: V
authors.lastname: Robert
mesh_terms: D000465:Algorithms; D044822:Biodiversity; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods; D066289:Data Curation; D066264:Datasets as Topic; D005656:Fungal Proteins / Q000737:chemistry / Q000235:genetics; D005658:Fungi / Q000145:classification* / Q000235:genetics; D058977:Molecular Sequence Annotation; D015203:Reproducibility of Results
chemical_list: D005656:Fungal Proteins