title: AlignBucket: a tool to speed up 'all-against-all' protein sequence alignments optimizing length constraints.
abstract: BACKGROUND
  The next-generation sequencing era requires reliable, fast and efficient approaches for the accurate annotation of the ever-increasing number of biological sequences and their variations. Transfer of annotation upon similarity search is a standard approach. The procedure of all-against-all protein comparison is a preliminary step of different available methods that annotate sequences based on information already present in databases. Given the actual volume of sequences, methods are necessary to pre-process data to reduce the time of sequence comparison.
  
  
  RESULTS
  We present an algorithm that optimizes the partition of a large volume of sequences (the whole database) into sets where sequence length values (in residues) are constrained depending on a bounded minimal and expected alignment coverage. The idea is to optimally group protein sequences according to their length, and then computing the all-against-all sequence alignments among sequences that fall in a selected length range. We describe a mathematically optimal solution and we show that our method leads to a 5-fold speed-up in real world cases.
  
  
  METHODS
  The software is available for downloading at http://www.biocomp.unibo.it/∼giuseppe/partitioning.html.
  
  
  BACKGROUND
  giuseppe.profiti2@unibo.it.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science and Engineering, via Mura Anteo Zamboni 7, Bologna, Bologna Biocomputing group, via S. Giacomo 9/2, Bologna and Health Sciences and Technologies ICIR, via Tolara di Sopra 41/E, Ozzano dell'Emilia, Italy.
authors.forename: Giuseppe
authors.initials: G
authors.lastname: Profiti
authors.affiliation: Department of Computer Science and Engineering, via Mura Anteo Zamboni 7, Bologna, Bologna Biocomputing group, via S. Giacomo 9/2, Bologna and.
authors.forename: Piero
authors.initials: P
authors.lastname: Fariselli
authors.affiliation: Bologna Biocomputing group, via S. Giacomo 9/2, Bologna and Health Sciences and Technologies ICIR, via Tolara di Sopra 41/E, Ozzano dell'Emilia, Italy.
authors.forename: Rita
authors.initials: R
authors.lastname: Casadio
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D006801:Humans; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins