Clustering 


Clustering search for term

In bioinformatics, sequence clustering algorithms attempt to group 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 and CD-HIT 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. (Wikipedia). Most clustering algorithms use an
agglomerative approach. The similarity criterion for clustering is usually stated in terms of minimum overlap and minimum percentage identity. There are two main approaches to find overlaps : looking at the edit distance (number of mutations needed to descibe the distance) or a k-mer counting approach. Two popular clustering algorithms are WCD (http://code.google.com/p/wcdest/) and d2_cluster (Burke et al 1999) (Edwards 2009)