Sequence clustering
In bioinformatics, sequence clustering algorithms attempt to group biological sequences that are somehow related. The sequences can be either of genomic, "transcriptomic" (ESTs) or protein origin. For proteins, homologous sequences are typically grouped into families. For EST data, clustering is important to group sequences originating from the same gene before the ESTs are assembled to reconstruct the original mRNA.
Some clustering algorithms use single-linkage clustering, constructing a transitive closure of sequences with a similarity over a particular threshold. UCLUST<ref name=usearch>Template:Cite web</ref> and CD-HIT<ref name=cdhit>Template:Cite web</ref> use a greedy algorithm that identifies a representative sequence for each cluster and assigns a new sequence to that cluster if it is sufficiently similar to the representative; if a sequence is not matched then it becomes the representative sequence for a new cluster. The similarity score is often based on sequence alignment. Sequence clustering is often used to make a non-redundant set of representative sequences.
Sequence clusters are often synonymous with (but not identical to) protein families. Determining a representative tertiary structure for each sequence cluster is the aim of many structural genomics initiatives.
Sequence clustering algorithms and packages
- CD-HIT<ref name=cdhit/>
- UCLUST in USEARCH<ref name=usearch/>
- Starcode:<ref>Template:Cite web</ref> a fast sequence clustering algorithm based on exact all-pairs search.<ref name="pmid25638815">Template:Cite journal</ref>
- OrthoFinder:<ref>Template:Cite web</ref> a fast, scalable and accurate method for clustering proteins into gene families (orthogroups)<ref name="pmid26243257">Template:Cite journal</ref><ref name="pmid31727128">Template:Cite journal</ref>
- Linclust:<ref name="pmid29959318">Template:Cite journal</ref> first algorithm whose runtime scales linearly with input set size, very fast, part of MMseqs2<ref name="pmid29035372">Template:Cite journal</ref> software suite for fast, sensitive sequence searching and clustering of large sequence sets
- TribeMCL: a method for clustering proteins into related groups<ref name="pmid11917018">Template:Cite journal</ref>
- BAG: a graph theoretic sequence clustering algorithm<ref>Template:Cite web</ref>
- JESAM:<ref>Template:Cite web</ref> Open source parallel scalable DNA alignment engine with optional clustering software component
- UICluster:<ref>Template:Cite web </ref> Parallel Clustering of EST (Gene) Sequences
- BLASTClust single-linkage clustering with BLAST<ref>Template:Cite web</ref>
- Clusterer:<ref>Template:Cite web</ref> extendable java application for sequence grouping and cluster analyses
- PATDB: a program for rapidly identifying perfect substrings
- nrdb:<ref>Template:Cite web</ref> a program for merging trivially redundant (identical) sequences
- CluSTr:<ref>Template:Cite web</ref> A single-linkage protein sequence clustering database from Smith-Waterman sequence similarities; covers over 7 mln sequences including UniProt and IPI
- ICAtools<ref>Template:Cite web</ref> - original (ancient) DNA clustering package with many algorithms useful for artifact discovery or EST clustering
- Skipredudant EMBOSS tool<ref>Template:Cite web</ref> to remove redundant sequences from a set
- CLUSS Algorithm<ref name="pmid17683581">Template:Cite journal</ref> to identify groups of structurally, functionally, or evolutionarily related hard-to-align protein sequences. CLUSS webserver <ref name="prospectus.usherbrooke.ca">Template:Cite web</ref>
- CLUSS2 Algorithm<ref name="pmid20058485">Template:Cite journal</ref> for clustering families of hard-to-align protein sequences with multiple biological functions. CLUSS2 webserver <ref name="prospectus.usherbrooke.ca"/>
Non-redundant sequence databases
- PISCES: A Protein Sequence Culling Server<ref>Template:Cite web</ref>
- RDB90<ref name=rdb90>Template:Cite journal</ref>
- UniRef: A non-redundant UniProt sequence database<ref>Template:Cite web</ref>
- Uniclust: A clustered UniProtKB sequences at the level of 90%, 50% and 30% pairwise sequence identity.<ref name="pmid27899574">Template:Cite journal</ref>
- Virus Orthologous Clusters:<ref>Template:Cite web</ref> A viral protein sequence clustering database; contains all predicted genes from eleven virus families organized into ortholog groups by BLASTP similarity