Send to

Choose Destination
PeerJ. 2014 Oct 7;2:e607. doi: 10.7717/peerj.607. eCollection 2014.

Speeding up all-against-all protein comparisons while maintaining sensitivity by considering subsequence-level homology.

Author information

University College London, London, United Kingdom.
Swiss Institute of Bioinformatics, Zurich, Switzerland.
ETH Zurich, Department of Computer Science, Zurich, Switzerland.
Contributed equally


Orthology inference and other sequence analyses across multiple genomes typically start by performing exhaustive pairwise sequence comparisons, a process referred to as "all-against-all". As this process scales quadratically in terms of the number of sequences analysed, this step can become a bottleneck, thus limiting the number of genomes that can be simultaneously analysed. Here, we explored ways of speeding-up the all-against-all step while maintaining its sensitivity. By exploiting the transitivity of homology and, crucially, ensuring that homology is defined in terms of consistent protein subsequences, our proof-of-concept resulted in a 4× speedup while recovering >99.6% of all homologs identified by the full all-against-all procedure on empirical sequences sets. In comparison, state-of-the-art k-mer approaches are orders of magnitude faster but only recover 3-14% of all homologous pairs. We also outline ideas to further improve the speed and recall of the new approach. An open source implementation is provided as part of the OMA standalone software at


All-against-all; Homology; Orthology; Sequence alignment; Smith–Waterman

Supplemental Content

Full text links

Icon for PeerJ, Inc. Icon for PubMed Central
Loading ...
Support Center