Sequence clustering

Last updated

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.

Contents

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

See also

References

  1. 1 2 "USEARCH". drive5.com.
  2. 1 2 "CD-HIT: a ultra-fast method for clustering protein and nucleotide sequences, with many new applications in next generation sequencing (NGS) data". cd-hit.org.
  3. "Starcode repository". GitHub . 2018-10-11.
  4. Zorita E, Cuscó P, Filion GJ (June 2015). "Starcode: sequence clustering based on all-pairs search". Bioinformatics. 31 (12): 1913–9. doi:10.1093/bioinformatics/btv053. PMC   4765884 . PMID   25638815.
  5. "OrthoFinder". Steve Kelly Lab.
  6. Emms DM, Kelly S (August 2015). "OrthoFinder: solving fundamental biases in whole genome comparisons dramatically improves orthogroup inference accuracy". Genome Biology. 16 (1) 157. doi: 10.1186/s13059-015-0721-2 . PMC   4531804 . PMID   26243257.
  7. Emms DM, Kelly S (November 2019). "OrthoFinder: phylogenetic orthology inference for comparative genomics". Genome Biology. 20 (1) 238. doi: 10.1186/s13059-019-1832-y . PMC   6857279 . PMID   31727128.
  8. Steinegger M, Söding J (June 2018). "Clustering huge protein sequence sets in linear time". Nature Communications. 9 (1) 2542. Bibcode:2018NatCo...9.2542S. doi:10.1038/s41467-018-04964-5. PMC   6026198 . PMID   29959318.
  9. Steinegger M, Söding J (November 2017). "MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets". Nature Biotechnology. 35 (11): 1026–1028. doi:10.1038/nbt.3988. hdl: 11858/00-001M-0000-002E-1967-3 . PMID   29035372. S2CID   402352.
  10. Enright AJ, Van Dongen S, Ouzounis CA (April 2002). "An efficient algorithm for large-scale detection of protein families". Nucleic Acids Research. 30 (7): 1575–84. doi:10.1093/nar/30.7.1575. PMC   101833 . PMID   11917018.
  11. "Archived copy". Archived from the original on 2003-12-06. Retrieved 2004-02-19.{{cite web}}: CS1 maint: archived copy as title (link)
  12. "Bioinformatics Paper: JESAM: CORBA software components for EST alignments and clusters". littlest.co.uk.
  13. "pedretti@eyeball -- Clustering Page". ratest.eng.uiowa.edu. Archived from the original on 2005-04-09.
  14. "NCBI News: Spring 2004-BLASTLab". nih.gov.
  15. "Clusterer: extendable java application for sequence grouping and cluster analyses". bugaco.com.
  16. "Index of /pub/nrdb". Archived from the original on 2008-01-01.
  17. "CluSTr". Archived from the original on 2006-09-24. Retrieved 2006-11-23.
  18. "Introduction to the ICAtools". littlest.co.uk.
  19. "EMBOSS: skipredundant". pasteur.fr.
  20. Kelil A, Wang S, Brzezinski R, Fleury A (August 2007). "CLUSS: clustering of protein sequences based on a new similarity measure". BMC Bioinformatics. 8 286. doi: 10.1186/1471-2105-8-286 . PMC   1976428 . PMID   17683581.
  21. 1 2 "CLUSS Home Page".
  22. Kelil A, Wang S, Brzezinski R (2008). "CLUSS2: an alignment-independent algorithm for clustering protein families with multiple biological functions". International Journal of Computational Biology and Drug Design. 1 (2): 122–40. doi:10.1504/ijcbdd.2008.020190. PMID   20058485.
  23. "Dunbrack Lab". fccc.edu.
  24. Holm L, Sander C (June 1998). "Removing near-neighbour redundancy from large protein sequence collections". Bioinformatics. 14 (5): 423–9. doi: 10.1093/bioinformatics/14.5.423 . PMID   9682055.
  25. "About UniProt". uniprot.org.
  26. Mirdita M, von den Driesch L, Galiez C, Martin MJ, Söding J, Steinegger M (January 2017). "Uniclust databases of clustered and deeply annotated protein sequences and alignments". Nucleic Acids Research. 45 (D1): D170 –D176. doi:10.1093/nar/gkw1081. PMC   5614098 . PMID   27899574.
  27. "VOCS - Viral Bioinformatics Resource Center". uvic.ca.