Sequence clustering: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
KolbertBot (talk | contribs)
Bots
1,166,042 edits
m Bot: HTTP→HTTPS (v485)
Line 76: Line 76:
* Virus Orthologous Clusters:<ref>{{cite web|url=http://athena.bioc.uvic.ca/tools/VOCS|title=VOCS - Viral Bioinformatics Resource Center|work=uvic.ca}}</ref> A viral protein sequence clustering database; contains all predicted genes from eleven virus families organized into ortholog groups by BLASTP similarity
* Virus Orthologous Clusters:<ref>{{cite web|url=http://athena.bioc.uvic.ca/tools/VOCS|title=VOCS - Viral Bioinformatics Resource Center|work=uvic.ca}}</ref> A viral protein sequence clustering database; contains all predicted genes from eleven virus families organized into ortholog groups by BLASTP similarity
* Skipredudant EMBOSS tool<ref>{{cite web|url=http://bioweb2.pasteur.fr/docs/EMBOSS/skipredundant.html|title=EMBOSS: skipredundant|work=pasteur.fr}}</ref> to remove redundant sequences from a set
* Skipredudant EMBOSS tool<ref>{{cite web|url=http://bioweb2.pasteur.fr/docs/EMBOSS/skipredundant.html|title=EMBOSS: skipredundant|work=pasteur.fr}}</ref> to remove redundant sequences from a set
* CLUSS<ref>http://prospectus.usherbrooke.ca/CLUSS/</ref> Algorithm<ref>{{cite web|url=https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-8-286|title=CLUSS Algorithm : Clustering non-alignable protein sequences|work=prospectus.usherbrooke.ca}}</ref> to identify groups of structurally, functionally, or evolutionarily related sequences.
<!-- Lets try the above (although both are wobbly) -->
<!-- Lets try the above (although both are wobbly) -->
<!-- * [http://bio.cc/RSDB RSDB] broken link -->
<!-- * [http://bio.cc/RSDB RSDB] broken link -->

Revision as of 20:45, 9 May 2018

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

  • Starcode:[3] a fast sequence clustering algorithm based on exact all-pairs search.[4]
  • OrthoFinder:[5] a fast, scalable and accurate method for clustering proteins into gene families (orthogroups)[6]
  • UCLUST in USEARCH[1]
  • CD-HIT[2]
  • Linclust: clustering protein sequences in linear time[7]
  • nrdb90.pl[8]
  • MMseqs2: software suite for fast and deep clustering of large protein sequence sets [9] [10]
  • TribeMCL: a method for clustering proteins into related groups[11]
  • BAG: a graph theoretic sequence clustering algorithm[12]
  • JESAM:[13] Open source parallel scalable DNA alignment engine with optional clustering software component
  • UICluster:[14] Parallel Clustering of EST (Gene) Sequences
  • BLASTClust single-linkage clustering with BLAST[15]
  • (Multi)netclust:[16] fast and memory-efficient detection of connected clusters in (multi-parametric) data networks[17]
  • Clusterer:[18] extendable java application for sequence grouping and cluster analyses
  • PATDB: a program for rapidly identifying perfect substrings
  • nrdb:[19] a program for merging trivially redundant (identical) sequences
  • CluSTr:[20] A single-linkage protein sequence clustering database from Smith-Waterman sequence similarities; covers over 7 mln sequences including UniProt and IPI
  • ICAtools[21] - original (ancient) DNA clustering package with many algorithms useful for artifact discovery or EST clustering
  • Virus Orthologous Clusters:[22] A viral protein sequence clustering database; contains all predicted genes from eleven virus families organized into ortholog groups by BLASTP similarity
  • Skipredudant EMBOSS tool[23] to remove redundant sequences from a set
  • CLUSS[24] Algorithm[25] to identify groups of structurally, functionally, or evolutionarily related sequences.

Non-redundant sequence databases

  • PISCES: A Protein Sequence Culling Server[26]
  • RDB90[8]
  • UniRef: A non-redundant UniProt sequence database[27]
  • Uniclust: A clustered UniProtKB sequences at the level of 90%, 50% and 30% pairwise sequence identity.[28]

See also

References

  1. ^ a b "USEARCH". drive5.com.
  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". cd-hit.org.
  3. ^ "Starcode repository".
  4. ^ Zorita E; Cuscó P; Filion GJ. (Jun 2015). "Starcode: sequence clustering based on all-pairs search". Bioinformatics. 31 (12): 1913–1919. doi:10.1093/bioinformatics/btv053. PMC 4765884. PMID 25638815.
  5. ^ "OrthoFinder". Steve Kelly Lab.
  6. ^ 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. PMC 4531804. PMID 26243257.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  7. ^ Steinegger, Martin; Soeding, Johannes (2017-05-25). "Linclust: clustering billions of protein sequences per day on a single server". bioRxiv 104034. {{cite bioRxiv}}: Check |biorxiv= value (help)
  8. ^ 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.{{cite journal}}: CS1 maint: numeric names: authors list (link)
  9. ^ Hauser M.; Steinegger M.; Söding J. (Jan 2016). "MMseqs software suite for fast and deep clustering and searching of large protein sequence sets". Bioinformatics. 32 (9): 1323–1330. doi:10.1093/bioinformatics/btw006. PMID 26743509.
  10. ^ Steinegger M.; Söding J. (Oct 16, 2017). "MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets". Nature Biotechnology. doi:10.1038/nbt.3988. PMID 29035372.
  11. ^ 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. PMC 101833. PMID 11917018.
  12. ^ http://bio.informatics.indiana.edu/sunkim/BAG/
  13. ^ "Bioinformatics Paper: JESAM: CORBA software components for EST alignments and clusters". littlest.co.uk.
  14. ^ http://ratest.eng.uiowa.edu/pubsoft/clustering/
  15. ^ "NCBI News: Spring 2004-BLASTLab". nih.gov.
  16. ^ "WUR Multi-netclust web server". bioinformatics.nl.
  17. ^ 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. PMC 2944197. PMID 20679333.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  18. ^ "Clusterer: extendable java application for sequence grouping and cluster analyses". bugaco.com.
  19. ^ https://web.archive.org/web/20080101032917/http://blast.wustl.edu/pub/nrdb/
  20. ^ http://www.ebi.ac.uk/clustr/
  21. ^ "Introduction to the ICAtools". littlest.co.uk.
  22. ^ "VOCS - Viral Bioinformatics Resource Center". uvic.ca.
  23. ^ "EMBOSS: skipredundant". pasteur.fr.
  24. ^ http://prospectus.usherbrooke.ca/CLUSS/
  25. ^ "CLUSS Algorithm : Clustering non-alignable protein sequences". prospectus.usherbrooke.ca.
  26. ^ "Dunbrack Lab". fccc.edu.
  27. ^ "About UniProt". uniprot.org.
  28. ^ Mirdita M; von den Drisch L.; Galiez C.; Soeding J.; Steinegger M. (Nov 2016). "Uniclust databases of clustered and deeply annotated protein sequences and alignments". Nucleic Acids Res. 45 (D1): D170–D176. doi:10.1093/nar/gkw1081.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Sequence_clustering&oldid=840428664"