Login
Login

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{{cite web|url=http://www.drive5.com/usearch|title=USEARCH|work=drive5.com}} and CD-HIT{{cite web|url=http://cd-hit.org|title=CD-HIT: a ultra-fast method for clustering protein and nucleotide sequences, with many new applications in next generation sequencing (NGS) data|work=cd-hit.org}} 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

{{directory|date=September 2018}}

  • CD-HIT
  • UCLUST in USEARCH
  • Starcode:{{cite web|url=https://github.com/gui11aume/starcode|title=Starcode repository|website=GitHub|date=2018-10-11}} a fast sequence clustering algorithm based on exact all-pairs search.{{cite journal | vauthors = Zorita E, Cuscó P, Filion GJ | title = Starcode: sequence clustering based on all-pairs search | journal = Bioinformatics | volume = 31 | issue = 12 | pages = 1913–9 | date = June 2015 | pmid = 25638815 | pmc = 4765884 | doi = 10.1093/bioinformatics/btv053 }}
  • OrthoFinder:{{cite web|url=http://www.stevekellylab.com/software/orthofinder|title=OrthoFinder|work=Steve Kelly Lab}} a fast, scalable and accurate method for clustering proteins into gene families (orthogroups){{cite journal | vauthors = Emms DM, Kelly S | title = OrthoFinder: solving fundamental biases in whole genome comparisons dramatically improves orthogroup inference accuracy | journal = Genome Biology | volume = 16 | pages = 157 | date = August 2015 | issue = 1 | pmid = 26243257 | pmc = 4531804 | doi = 10.1186/s13059-015-0721-2 | doi-access = free }}{{cite journal | vauthors = Emms DM, Kelly S | title = OrthoFinder: phylogenetic orthology inference for comparative genomics | journal = Genome Biology | volume = 20 | issue = 1 | pages = 238 | date = November 2019 | pmid = 31727128 | pmc = 6857279 | doi = 10.1186/s13059-019-1832-y | doi-access = free }}
  • Linclust:{{cite journal | vauthors = Steinegger M, Söding J | title = Clustering huge protein sequence sets in linear time | journal = Nature Communications | volume = 9 | issue = 1 | pages = 2542 | date = June 2018 | pmid = 29959318 | pmc = 6026198 | doi = 10.1038/s41467-018-04964-5 | bibcode = 2018NatCo...9.2542S }} first algorithm whose runtime scales linearly with input set size, very fast, part of [http://mmseqs.org/ MMseqs2]{{cite journal | vauthors = Steinegger M, Söding J | title = MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets | journal = Nature Biotechnology | volume = 35 | issue = 11 | pages = 1026–1028 | date = November 2017 | pmid = 29035372 | doi = 10.1038/nbt.3988 | hdl = 11858/00-001M-0000-002E-1967-3 | s2cid = 402352 | hdl-access = free }} software suite for fast, sensitive sequence searching and clustering of large sequence sets
  • TribeMCL: a method for clustering proteins into related groups{{cite journal | vauthors = Enright AJ, Van Dongen S, Ouzounis CA | title = An efficient algorithm for large-scale detection of protein families | journal = Nucleic Acids Research | volume = 30 | issue = 7 | pages = 1575–84 | date = April 2002 | pmid = 11917018 | pmc = 101833 | doi = 10.1093/nar/30.7.1575 }}
  • BAG: a graph theoretic sequence clustering algorithm{{cite web |url=http://bio.informatics.indiana.edu/sunkim/BAG/ |title=Archived copy |access-date=2004-02-19 |url-status=dead |archive-url=https://web.archive.org/web/20031206172749/http://bio.informatics.indiana.edu/sunkim/BAG/ |archive-date=2003-12-06 }}
  • JESAM:{{cite web|url=http://www.littlest.co.uk/software/bioinf/old_packages/jesam/jesam_paper.html|title=Bioinformatics Paper: JESAM: CORBA software components for EST alignments and clusters|work=littlest.co.uk}} Open source parallel scalable DNA alignment engine with optional clustering software component
  • UICluster:{{cite web |url=http://ratest.eng.uiowa.edu/pubsoft/clustering/ |title=pedretti@eyeball -- Clustering Page |website=ratest.eng.uiowa.edu |url-status=dead |archive-url=https://web.archive.org/web/20050409134817/http://ratest.eng.uiowa.edu/pubsoft/clustering/ |archive-date=2005-04-09}} Parallel Clustering of EST (Gene) Sequences
  • BLASTClust single-linkage clustering with BLAST{{cite web|url=https://www.ncbi.nlm.nih.gov/Web/Newsltr/Spring04/blastlab.html|title=NCBI News: Spring 2004-BLASTLab|work=nih.gov}}
  • Clusterer:{{cite web|url=http://bugaco.com/bioinf/clusterer/|title=Clusterer: extendable java application for sequence grouping and cluster analyses|work=bugaco.com}} extendable java application for sequence grouping and cluster analyses
  • PATDB: a program for rapidly identifying perfect substrings
  • nrdb:{{Cite web | url=http://blast.wustl.edu/pub/nrdb/ | title=Index of /pub/nrdb| archive-url=https://web.archive.org/web/20080101032917/http://blast.wustl.edu/pub/nrdb/| archive-date=2008-01-01}} a program for merging trivially redundant (identical) sequences
  • CluSTr:{{cite web |url=http://www.ebi.ac.uk/clustr/ |title=CluSTr |access-date=2006-11-23 |url-status=dead |archive-url=https://web.archive.org/web/20060924012903/http://www.ebi.ac.uk/clustr/ |archive-date=2006-09-24 }} A single-linkage protein sequence clustering database from Smith-Waterman sequence similarities; covers over 7 mln sequences including UniProt and IPI
  • ICAtools{{cite web|url=http://www.littlest.co.uk/software/bioinf/old_packages/icatools/|title=Introduction to the ICAtools|work=littlest.co.uk}} - original (ancient) DNA clustering package with many algorithms useful for artifact discovery or EST clustering
  • Skipredudant EMBOSS tool{{cite web|url=http://bioweb2.pasteur.fr/docs/EMBOSS/skipredundant.html|title=EMBOSS: skipredundant|work=pasteur.fr}} to remove redundant sequences from a set
  • CLUSS Algorithm{{cite journal | vauthors = Kelil A, Wang S, Brzezinski R, Fleury A | title = CLUSS: clustering of protein sequences based on a new similarity measure | journal = BMC Bioinformatics | volume = 8 | pages = 286 | date = August 2007 | pmid = 17683581 | pmc = 1976428 | doi = 10.1186/1471-2105-8-286 | doi-access = free }} to identify groups of structurally, functionally, or evolutionarily related hard-to-align protein sequences. CLUSS webserver {{Cite web | url=http://prospectus.usherbrooke.ca/CLUSS/ | title=CLUSS Home Page}}
  • CLUSS2 Algorithm{{cite journal | vauthors = Kelil A, Wang S, Brzezinski R | title = CLUSS2: an alignment-independent algorithm for clustering protein families with multiple biological functions | journal = International Journal of Computational Biology and Drug Design | volume = 1 | issue = 2 | pages = 122–40 | date = 2008 | pmid = 20058485 | doi = 10.1504/ijcbdd.2008.020190 }} for clustering families of hard-to-align protein sequences with multiple biological functions. CLUSS2 webserver

Non-redundant sequence databases

  • PISCES: A Protein Sequence Culling Server{{cite web|url=http://dunbrack.fccc.edu/pisces/|title=Dunbrack Lab|work=fccc.edu}}
  • RDB90{{cite journal | vauthors = Holm L, Sander C | title = Removing near-neighbour redundancy from large protein sequence collections | journal = Bioinformatics | volume = 14 | issue = 5 | pages = 423–9 | date = June 1998 | pmid = 9682055 | doi = 10.1093/bioinformatics/14.5.423 | doi-access = free }}
  • UniRef: A non-redundant UniProt sequence database{{cite web|url=https://www.uniprot.org/database/DBDescription.shtml#uniref|title=About UniProt|work=uniprot.org}}
  • Uniclust: A clustered UniProtKB sequences at the level of 90%, 50% and 30% pairwise sequence identity.{{cite journal | vauthors = Mirdita M, von den Driesch L, Galiez C, Martin MJ, Söding J, Steinegger M | title = Uniclust databases of clustered and deeply annotated protein sequences and alignments | journal = Nucleic Acids Research | volume = 45 | issue = D1 | pages = D170–D176 | date = January 2017 | pmid = 27899574 | pmc = 5614098 | doi = 10.1093/nar/gkw1081 }}
  • Virus Orthologous Clusters:{{cite web|url=http://athena.bioc.uvic.ca/tools/VOCS|title=VOCS - Viral Bioinformatics Resource Center|work=uvic.ca}} A viral protein sequence clustering database; contains all predicted genes from eleven virus families organized into ortholog groups by BLASTP similarity

See also

References

{{reflist}}

Category:Bioinformatics