Vector Quantized Spectral Clustering Applied to Whole Genome Sequences of Plants. (March 2019)

• Record Type: Journal Article
• Authors: Shastri, Aditya A; Ahuja, Kapil; Ratnaparkhe, Milind B; Shah, Aditya; Gagrani, Aishwary; Lal, Anant
• Is Part Of: Evolutionary bioinformatics online. Volume 15(2019)
• Publication Date: 2019-03
• Subjects: spectral clustering -- similarity matrix -- alignment score -- sampling -- vector quantization -- k-medoids -- whole genome sequence (WGS) -- single nucleotide polymorphism (SNP); Bioinformatics -- Periodicals; Evolutionary computation -- Periodicals; Genetic programming (Computer science) -- Periodicals; Computational Biology; Evolution, Molecular; Bioinformatics; Electronic journals; Periodicals; Fulltext; Internet Resources; Periodicals; Periodicals; 576.8
• DOI: 10.1177/1176934319836997
• Languages: English
• ISSNs: 1176-9343

Abstract

We develop a Vector Quantized Spectral Clustering (VQSC) algorithm that is a combination of spectral clustering (SC) and vector quantization (VQ) sampling for grouping genome sequences of plants. The inspiration here is to use SC for its accuracy and VQ to make the algorithm computationally cheap (the complexity of SC is cubic in terms of the input size). Although the combination of SC and VQ is not new, the novelty of our work is in developing the crucial similarity matrix in SC as well as use of k -medoids in VQ, both adapted for the plant genome data. For Soybean, we compare our approach with commonly used techniques like Un-weighted Pair Graph Method with Arithmetic mean (UPGMA) and Neighbor Joining (NJ). Experimental results show that our VQSC outperforms both these techniques significantly in terms of cluster quality (average improvement of 21% over UPGMA and 24% over NJ) as well as time complexity (order of magnitude faster than both UPGMA and NJ).