Environmental metagenomic studies are a rich source for genetic diversity. Terabytes of short read sequencing data are publicly available and the growth rate has increased steadily, with the rate of exponential decrease in costs and increase in throughput outperforming Moore's law two-fold in the last decade. Now, not the creation of the data but their analysis is the main time and cost bottleneck. Crucial for sequence data analysis are the sequence clustering and homology search steps for the functional annotation of the discovered open reading frames (ORFs). Clustering protein sequences can considerably reduce the redundancy of sequence sets and costs of downstream analysis and storage. Clustering can also be used to define protein families when clustering to lower sequence identities. We propose two clustering methods: (1) MMseqs, a fast and sensitive clustering method, and (2) Linclust, the first sequence e clustering algorithm whose runtime scales linearly with the number of sequences and independent of the numbers of clusters obtained. MMseqs is a very sensitive all-against-all search based clustering algorithm that can cluster protein sets down to 30% sequence identity while remaining more sensitive and faster than other state of the art methods. MMseqs computes a similarity graph by self comparison of the protein set and then uses a greedy set cover algorithm to cluster the graph. This approach reduces the number of clusters compared to the state of the art greedy clustering. Sequence search is used to annotate novel sequences by homology inference from known sequences. Fast sequence search methods trade sensitivity for runtime speed. We developed MMseqs2 an successor of MMseqs. Our method can perform sequence searches as sensitive as BLAST and profile searches even more sensitive than PSI-BLAST, but two to three orders of magnitude faster. MMseqs2 also supports fast reverse profile searches, which we used to annotate 1.1 billion metagenomic protein sequence in 8.3 hours on a single 28 CPU core computer. The speed and sensitivity of MMseqs2 should makes it a powerful tool to annotate protein sequence in the era of big metagenomics data. State of the art sequence clustering methods scale nearly quadratically O(NK) where N is the input set size and K are the amount of clusters. Linclust is the first algorithm that overcomes the dependency of K and run in linear time O(N). Linclust can cluster protein sets down to 50% sequence identity three to four orders of magnitude faster than other methods. We clustered 1.6 billion protein sequence from about ~2200 metagenome and metatranscriptome assemblies down to 50% sequence identity using Linclust, which took 14 hours on a single server with 28 CPU cores.     «

Environmental metagenomic studies are a rich source for genetic diversity. Terabytes of short read sequencing data are publicly available and the growth rate has increased steadily, with the rate of exponential decrease in costs and increase in throughput outperforming Moore's law two-fold in the last decade. Now, not the creation of the data but their analysis is the main time and cost bottleneck. Crucial for sequence data analysis are the sequence clustering and homology search steps for the f...     »

Metagenomische studien sind eine reiche Quelle für genetische Vielfalt. Terabyte von Sequenzierungsdaten sind öffentlich verfügbar und wachsen stetig. Dies kommt von der exponentiellen Abnahme der Kosten und der Erhöhung des Durchsatzes von Sequenzierern. Die technische Entwicklung der Sequenzierung hat das Mooresche Gesetz in den letzten zehn Jahren um ein Zweifaches übertroffen. Aktuell ist nicht mehr die Erzeugung, sondern die Datenanalyse der größte Zeit- und Kostenfaktor. Entscheidend für die Datenanalyse sind das Clustern und die Homologiesuchen von Sequenzen. Clustering-Proteinsequenzen kann Redundanz in Sequenzdaten reduzieren und somit die Kosten der nachgeschalteten Analyse und Speicherung erheblich reduzieren. Durch das Clustering auf niedrige Sequenzidentitäten können wir auch Proteinfamilien definieren. In dieser Arbeit stellen wir zwei Clustering-Methoden vor: (1) MMseqs, eine schnelle und sensitive Clustering-Methode, und (2) Linclust, der erste Sequenzclustering Algorithmus, dessen Laufzeit linear mit der Anzahl der Sequenzen und unabhängig von der Anzahl der Cluster wächst. MMseqs ist ein sehr sensitiver Clustering-Algorithmus der auf einer Alle-Gegen-Alle Suche basiert, welche Proteinsequenzen bis auf 30\% Sequenzidentität clustern kann. Die Methode ist empfindlicher und schneller als andere aktuelle Methoden. MMseqs berechnet erst einen Ähnlichkeitsgraph durch Selbstvergleiche der Proteinsequenzen und verwendet dann einen Greedy-Set-Cover-Algorithmus, um den Graphen zu clustern. Dieser Ansatz reduziert die Anzahl der Cluster im weiter als andere moderne Methoden. Sequenzsuchen werden verwendet um neue Sequenzen durch Homologieinferenz durch schon bekannten Sequenzen zu annotieren. Schnelle moderne Sequenzsuchmethoden tauschen Empfindlichkeit für Geschwindigkeit. Mit MMseqs2, dem Nachfolger von MMseqs haben wir eine Methode entwickelt die Sequenzsuchen so empfindlich wie BLAST- und Profilsuchen so empfindlicher wie PSI-BLAST, jedoch zwei bis drei Größenordnungen schneller, durchführen kann. MMseqs2 unterstützt auch schnelle Umgedrehte-Profil-Suchen, mit denen wir 1,1 Milliarden metagenomische Proteinsequenzen in 8,3 Stunden auf einem einzigen 28 Kern Computer annotieren. Die Geschwindigkeit und Empfindlichkeit von MMseqs2 sollte es zu einem leistungsfähigen Werkzeug machen, um metagenomische Proteinsequenz zu annotieren. Aktuelle Sequenz-Clustering Methoden skalieren fast quadratisch O(NK), wobei N die Anzahl der Eingabesequenzen und K die Anzahl der Cluster sind. Linclust ist der erste Algorithmus, der die Abhängigkeit von K überwindet und in linearer Zeit O(N) läuft. Linclust kann Proteinsequenzen bis zu 50% der Sequenzidentität drei bis vier Größenordnungen schneller als andere Methoden clustern. Wir haben 1,6 Milliarden Proteinsequenzen von etwa 2200 Metagenom- und Metatranscriptom- Assemblierungen mit Linclust auf 50% Sequenzidentität geclustert, was 14 Stunden auf einem einzelnen Server mit 28 Kernen gedauert hat.     «

Metagenomische studien sind eine reiche Quelle für genetische Vielfalt. Terabyte von Sequenzierungsdaten sind öffentlich verfügbar und wachsen stetig. Dies kommt von der exponentiellen Abnahme der Kosten und der Erhöhung des Durchsatzes von Sequenzierern. Die technische Entwicklung der Sequenzierung hat das Mooresche Gesetz in den letzten zehn Jahren um ein Zweifaches übertroffen. Aktuell ist nicht mehr die Erzeugung, sondern die Datenanalyse der größte Zeit- und Kostenfaktor. Entscheidend für d...     »