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

Related Research Articles

In the field of bioinformatics, a sequence database is a type of biological database that is composed of a large collection of computerized ("digital") nucleic acid sequences, protein sequences, or other polymer sequences stored on a computer. The UniProt database is an example of a protein sequence database. As of 2013 it contained over 40 million sequences and is growing at an exponential rate. Historically, sequences were published in paper form, but as the number of sequences grew, this storage method became unsustainable.

Protein family Group of evolutionarily-related proteins

A protein family is a group of evolutionarily related proteins. In many cases, a protein family has a corresponding gene family, in which each gene encodes a corresponding protein with a 1:1 relationship. The term "protein family" should not be confused with family as it is used in taxonomy.

Structural alignment Aligning molecular sequences using sequence and structural information

Structural alignment attempts to establish homology between two or more polymer structures based on their shape and three-dimensional conformation. This process is usually applied to protein tertiary structures but can also be used for large RNA molecules. In contrast to simple structural superposition, where at least some equivalent residues of the two structures are known, structural alignment requires no a priori knowledge of equivalent positions. Structural alignment is a valuable tool for the comparison of proteins with low sequence similarity, where evolutionary relationships between proteins cannot be easily detected by standard sequence alignment techniques. Structural alignment can therefore be used to imply evolutionary relationships between proteins that share very little common sequence. However, caution should be used in using the results as evidence for shared evolutionary ancestry because of the possible confounding effects of convergent evolution by which multiple unrelated amino acid sequences converge on a common tertiary structure.

Sequence homology Shared ancestry between DNA, RNA or protein sequences

Sequence homology is the biological homology between DNA, RNA, or protein sequences, defined in terms of shared ancestry in the evolutionary history of life. Two segments of DNA can have shared ancestry because of three phenomena: either a speciation event (orthologs), or a duplication event (paralogs), or else a horizontal gene transfer event (xenologs).

UniProt Database of protein sequences and functional information

UniProt is a freely accessible database of protein sequence and functional information, many entries being derived from genome sequencing projects. It contains a large amount of information about the biological function of proteins derived from the research literature. It is maintained by the UniProt consortium, which consists of several European bioinformatics organisations and a foundation from Washington, DC, United States.

Clustal

Clustal is a series of widely used computer programs used in bioinformatics for multiple sequence alignment. There have been many versions of Clustal over the development of the algorithm that are listed below. The analysis of each tool and its algorithm are also detailed in their respective categories. Available operating systems listed in the sidebar are a combination of the software availability and may not be supported for every current version of the Clustal tools. Clustal Omega has the widest variety of operating systems out of all the Clustal tools.

The European Bioinformatics Institute (EMBL-EBI) is an Intergovernmental Organization (IGO) which, as part of the European Molecular Biology Laboratory (EMBL) family, focuses on research and services in bioinformatics. It is located on the Wellcome Genome Campus in Hinxton near Cambridge, and employs over 600 full-time equivalent (FTE) staff. Institute leaders such as Rolf Apweiler, Alex Bateman, Ewan Birney, and Guy Cochrane, an adviser on the National Genomics Data Center Scientific Advisory Board, serve as part of the international research network of the BIG Data Center at the Beijing Institute of Genomics.

Computational genomics refers to the use of computational and statistical analysis to decipher biology from genome sequences and related data, including both DNA and RNA sequence as well as other "post-genomic" data. These, in combination with computational and statistical approaches to understanding the function of the genes and statistical association analysis, this field is also often referred to as Computational and Statistical Genetics/genomics. As such, computational genomics may be regarded as a subset of bioinformatics and computational biology, but with a focus on using whole genomes to understand the principles of how the DNA of a species controls its biology at the molecular level and beyond. With the current abundance of massive biological datasets, computational studies have become one of the most important means to biological discovery.

Protein threading, also known as fold recognition, is a method of protein modeling which is used to model those proteins which have the same fold as proteins of known structures, but do not have homologous proteins with known structure. It differs from the homology modeling method of structure prediction as it is used for proteins which do not have their homologous protein structures deposited in the Protein Data Bank (PDB), whereas homology modeling is used for those proteins which do. Threading works by using statistical knowledge of the relationship between the structures deposited in the PDB and the sequence of the protein which one wishes to model.

Multiple sequence alignment Alignment of more than two molecular sequence

Multiple sequence alignment (MSA) may refer to the process or the result of sequence alignment of three or more biological sequences, generally protein, DNA, or RNA. In many cases, the input set of query sequences are assumed to have an evolutionary relationship by which they share a linkage and are descended from a common ancestor. From the resulting MSA, sequence homology can be inferred and phylogenetic analysis can be conducted to assess the sequences' shared evolutionary origins. Visual depictions of the alignment as in the image at right illustrate mutation events such as point mutations that appear as differing characters in a single alignment column, and insertion or deletion mutations that appear as hyphens in one or more of the sequences in the alignment. Multiple sequence alignment is often used to assess sequence conservation of protein domains, tertiary and secondary structures, and even individual amino acids or nucleotides.

InterPro is a database of protein families, domains and functional sites in which identifiable features found in known proteins can be applied to new protein sequences in order to functionally characterise them.

This list of structural comparison and alignment software is a compilation of software tools and web portals used in pairwise or multiple structural comparison and structural alignment.

Circular permutation in proteins Arrangement of amino acid sequence

A circular permutation is a relationship between proteins whereby the proteins have a changed order of amino acids in their peptide sequence. The result is a protein structure with different connectivity, but overall similar three-dimensional (3D) shape. In 1979, the first pair of circularly permuted proteins – concanavalin A and lectin – were discovered; over 2000 such proteins are now known.

The HH-suite is an open-source software package for sensitive protein sequence searching. It contains programs that can search for similar protein sequences in protein sequence databases. Sequence searches are a standard tool in modern biology with which the function of unknown proteins can be inferred from the functions of proteins with similar sequences. HHsearch and HHblits are two main programs in the package and the entry point to its search function, the latter being a faster iteration. HHpred is an online server for protein structure prediction that uses homology information from HH-suite.

In bioinformatics, alignment-free sequence analysis approaches to molecular sequence and structure data provide alternatives over alignment-based approaches.

UCLUST is an algorithm designed to cluster nucleotide or amino-acid sequences into clusters based on sequence similarity. The algorithm was published in 2010 and implemented in a program also named UCLUST. The algorithm is described by the author as following two simple clustering criteria, in regard to the requested similarity threshold T. The first criterion states that any given cluster's centroid sequence will have a similarity smaller than T to any other clusters' centroid sequence. The second criterion states that each member sequence in a given cluster will have similarity to the cluster's centroid sequence that is equal or greater than T.

In molecular phylogenetics, relationships among individuals are determined using character traits, such as DNA, RNA or protein, which may be obtained using a variety of sequencing technologies. High-throughput next-generation sequencing has become a popular technique in transcriptomics, which represent a snapshot of gene expression. In eukaryotes, making phylogenetic inferences using RNA is complicated by alternative splicing, which produces multiple transcripts from a single gene. As such, a variety of approaches may be used to improve phylogenetic inference using transcriptomic data obtained from RNA-Seq and processed using computational phylogenetics.

Protein tandem repeats

An array of protein tandem repeats is defined as several adjacent copies having the same or similar sequence motifs. These periodic sequences are generated by internal duplications in both coding and non-coding genomic sequences. Repetitive units of protein tandem repeats are considerably diverse, ranging from the repetition of a single amino acid to domains of 100 or more residues.

OrthoFinder

OrthoFinder is a command-line software tool for comparative genomics. OrthoFinder determines the correspondence between genes in different organisms. This correspondence provides a framework for understanding the evolution of life on Earth, and enables the extrapolation and transfer of biological knowledge between organisms.

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: 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. "Archived copy". Archived from the original on 2006-09-24. Retrieved 2006-11-23.{{cite web}}: CS1 maint: archived copy as title (link)
  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.