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[1] and CD-HIT[2] 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

Non-redundant sequence databases

  • PISCES: A Protein Sequence Culling Server[8]
  • RDB90[4]
  • UniRef: A non-redundant UniProt sequence database[9]

See also

References

  1. ^ a b USEARCH: An exceptionally fast sequence clustering program for nucleotide and protein sequences
  2. ^ a b CD-HIT: a ultra-fast method for clustering protein and nucleotide sequences, with many new applications in next generation sequencing (NGS) data
  3. ^ Emms DM, Kelly S. (Aug 2015). "OrthoFinder: solving fundamental biases in whole genome comparisons dramatically improves orthogroup inference accuracy.". Genome Biology. 16 (157). doi:10.1186/s13059-015-0721-2. PMID 26243257. 
  4. ^ a b Holm L1, Sander C. (Jun 1998). "Removing near-neighbour redundancy from large protein sequence collections.". Bioinformatics 14 (5): 423–9. doi:10.1093/bioinformatics/14.5.423. PMID 9682055. 
  5. ^ Enright AJ, Van Dongen S, Ouzounis CA. (Apr 2002). "An efficient algorithm for large-scale detection of protein families.". Nucleic Acids Res. 30 (7): 1575–84. doi:10.1093/nar/30.7.1575. PMID 11917018. 
  6. ^ http://bio.informatics.indiana.edu/sunkim/BAG/
  7. ^ Kuzniar, A., Dhir, S., Nijveen, H., Pongor, S. and Leunissen, J. A. M. (Oct 2010). "Multi-netclust: an efficient tool for finding connected clusters in multi-parametric networks". Bioinformatics 26 (19): 2482–2483. doi:10.1093/bioinformatics/btq435. PMID 20679333. 
  8. ^ http://dunbrack.fccc.edu/pisces/
  9. ^ UniRef: A non-redundant UniProt sequence database