{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T10:33:20Z","timestamp":1724927600576},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Microb Informatics Exp"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Comparative genomics has put additional demands on the assessment of similarity between sequences and their clustering as means for classification. However, defining the optimal number of clusters, cluster density and boundaries for sets of potentially related sequences of genes with variable degrees of polymorphism remains a significant challenge. The aim of this study was to develop a method that would identify the cluster centroids and the optimal number of clusters for a given sensitivity level and could work equally well for the different sequence datasets.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>A novel method that combines the linear mapping hash function and multiple sequence alignment (MSA) was developed. This method takes advantage of the already sorted by similarity sequences from the MSA output, and identifies the optimal number of clusters, clusters cut-offs, and clusters centroids that can represent reference gene vouchers for the different species. The linear mapping hash function can map an already ordered by similarity distance matrix to indices to reveal gaps in the values around which the optimal cut-offs of the different clusters can be identified. The method was evaluated using sets of closely related (16S rRNA gene sequences of <jats:italic>Nocardia<\/jats:italic> species) and highly variable (VP1 genomic region of Enterovirus 71) sequences and outperformed existing unsupervised machine learning clustering methods and dimensionality reduction methods. This method does not require prior knowledge of the number of clusters or the distance between clusters, handles clusters of different sizes and shapes, and scales linearly with the dataset.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The combination of MSA with the linear mapping hash function is a computationally efficient way of gene sequence clustering and can be a valuable tool for the assessment of similarity, clustering of different microbial genomes, identifying reference sequences, and for the study of evolution of bacteria and viruses.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/2042-5783-2-2","type":"journal-article","created":{"date-parts":[[2012,1,26]],"date-time":"2012-01-26T07:23:52Z","timestamp":1327562632000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear normalised hash function for clustering gene sequences and identifying reference sequences from multiple sequence alignments"],"prefix":"10.1186","volume":"2","author":[{"given":"Manal","family":"Helal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fanrong","family":"Kong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharon CA","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominic E","family":"Dwyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Potter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitali","family":"Sintchenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,1,26]]},"reference":[{"issue":"7","key":"15_CR1","doi-asserted-by":"publisher","first-page":"2567","DOI":"10.1073\/pnas.0409727102","volume":"102","author":"KT Konstantinidis","year":"2005","unstructured":"Konstantinidis KT, Tiedje JM: Genomic insights that advance the species definition for prokaryotes. Proc Natl Acad Sci USA. 2005, 102 (7): 2567-2572. 10.1073\/pnas.0409727102.","journal-title":"Proc Natl Acad Sci USA"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1016\/j.mib.2006.08.008","volume":"9","author":"D Field","year":"2006","unstructured":"Field D, Wilson G, van der Gast C: How do we compare hundreds of bacterial genomes?. Cur Opin Microbiol. 2006, 9: 499-504. 10.1016\/j.mib.2006.08.008.","journal-title":"Cur Opin Microbiol"},{"issue":"5","key":"15_CR3","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1080\/10635150500354886","volume":"54","author":"PDN Hebert","year":"2005","unstructured":"Hebert PDN, Gregory TR: The promise of DNA barcoding for taxonomy. System Biol. 2005, 54 (5): 852-859. 10.1080\/10635150500354886.","journal-title":"System Biol"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.meegid.2008.05.005","volume":"8","author":"L Frezal","year":"2008","unstructured":"Frezal L, Leblois R: Four years of DNA barcoding: Current advances and prospects. Infec Genet Evol. 2008, 8: 727-736. 10.1016\/j.meegid.2008.05.005.","journal-title":"Infec Genet Evol"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1186\/1471-2105-9-546","volume":"9","author":"F Zhou","year":"2008","unstructured":"Zhou F, Olman V, Xu Y: Barcodes for genomes and applications. BMC Bioinform. 2008, 9: 546-10.1186\/1471-2105-9-546.","journal-title":"BMC Bioinform"},{"issue":"5","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"RC Edgar","year":"2004","unstructured":"Edgar RC: MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucl Acids Res. 2004, 32 (5): 1792-1797. 10.1093\/nar\/gkh340.","journal-title":"Nucl Acids Res"},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","volume":"15","author":"JD Thompson","year":"1999","unstructured":"Thompson JD, Plewniak F, Poch O: BAliBASE: A Benchmark Alignment Database for the Evaluation of Multiple Alignment Programs. Bioinformatics. 1999, 15 (1): 87-88. 10.1093\/bioinformatics\/15.1.87.","journal-title":"Bioinformatics"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1126\/science.1151532","volume":"319","author":"KM Wong","year":"2008","unstructured":"Wong KM, Suchard MA, Huelsenbeck JP: Alignment uncertainty and genomic analysis. Science. 2008, 319: 473-476. 10.1126\/science.1151532.","journal-title":"Science"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"2191","DOI":"10.1093\/bioinformatics\/bti368","volume":"21","author":"L Lancashire","year":"2005","unstructured":"Lancashire L, Schmid O, Shah H, Ball G: Classification of bacterial species from proteomic data using combinatorial approaches incorporating artificial neural networks, cluster analysis and principal component analysis. Bioinformatics. 2005, 21: 2191-2199. 10.1093\/bioinformatics\/bti368.","journal-title":"Bioinformatics"},{"key":"15_CR10","volume-title":"Survey of Clustering Data Mining Techniques","author":"P Berkhin","year":"2002","unstructured":"Berkhin P: Survey of Clustering Data Mining Techniques. 2002, Accrue Software, Inc"},{"issue":"4","key":"15_CR11","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A Yao","year":"1982","unstructured":"Yao A: On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J Comput. 1982, 11 (4): 721-736. 10.1137\/0211059.","journal-title":"SIAM J Comput"},{"key":"15_CR12","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801","volume-title":"Finding Groups in Data: An Introduction to Cluster Analysis","author":"L Kaufman","year":"1990","unstructured":"Kaufman L, Rousseeuw P: Finding Groups in Data: An Introduction to Cluster Analysis. 1990, John Wiley and Sons, New York, NY"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1093\/comjnl\/16.1.30","volume":"16","author":"R Sibson","year":"1973","unstructured":"Sibson R: SLINK: An optimally efficient algorithm for the single link cluster method. Computer J. 1973, 16: 30-34. 10.1093\/comjnl\/16.1.30.","journal-title":"Computer J"},{"key":"15_CR14","first-page":"73","volume-title":"CURE: An efficient clustering algorithm for large databases","author":"S Guha","year":"1998","unstructured":"Guha S, Rastogi R, Shim K: CURE: An efficient clustering algorithm for large databases. 1998, Proceedings of the ACM SIGMOD Conference, Seattle, WA, 73-84."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/2.781637","volume":"32","author":"G Karypis","year":"1999","unstructured":"Karypis G, Han E-H, Kumar V: CHAMELEON: A hierarchical clustering algorithm using dynamic modelling. IEEE Computer. 1999, 32: 68-75. 10.1109\/2.781637.","journal-title":"IEEE Computer"},{"issue":"4","key":"15_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1023\/A:1009740529316","volume":"2","author":"DL Boley","year":"1998","unstructured":"Boley DL: Principal direction divisive partitioning. Data Min Knowl Disc. 1998, 2 (4): 325-344. 10.1023\/A:1009740529316.","journal-title":"Data Min Knowl Disc"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"W470","DOI":"10.1093\/nar\/gkn277","volume":"36","author":"BE Dutilh","year":"2008","unstructured":"Dutilh BE, He Y, Hekkelman ML, Huynen MA: Signature, a web server for taxonomic characterization of sequence samples using signature genes. Nucl Acids Res. 2008, 36: W470-W474. 10.1093\/nar\/gkn277.","journal-title":"Nucl Acids Res"},{"key":"15_CR18","first-page":"37","volume-title":"In the Proceedings of the 7th Australian Joint Conference on Artificial Intelligence, UNE, World Scientific Publishing Co, Armidale, Australia","author":"C Wallace","year":"1994","unstructured":"Wallace C, Dowe D: Intrinsic classification by MML - the Snob program. In the Proceedings of the 7th Australian Joint Conference on Artificial Intelligence, UNE, World Scientific Publishing Co, Armidale, Australia. 1994, 37-44."},{"key":"15_CR19","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"P Cheeseman","year":"1996","unstructured":"Cheeseman P, Stutz J: Bayesian Classification (AutoClass): Theory and Results. Advances in Knowledge Discovery and Data Mining. Edited by: Fayyad UM, Piatetsky-Shapiro G, Smyth P, Uthurusamy R. 1996, AAAI Press\/MIT Press"},{"key":"15_CR20","volume-title":"MCLUST: Software for model-based cluster and discriminant analysis","author":"C Fraley","year":"1999","unstructured":"Fraley C, Raftery A: MCLUST: Software for model-based cluster and discriminant analysis. 1999, Tech Report 342. Dept. Statistics, Univ. of Washington"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"100","DOI":"10.2307\/2346830","volume":"28","author":"JA Hartigan","year":"1978","unstructured":"Hartigan JA, Wong MA: Algorithm AS 136: a K-means clustering algorithm. Appl Stat. 1978, 28: 100-108.","journal-title":"Appl Stat"},{"key":"15_CR22","volume-title":"Proceedings of the 17th ICML, Stanford University","author":"D Pelleg","year":"2000","unstructured":"Pelleg D, Moore A: X-means: Extending K-means with Efficient Estimation of the Number of Clusters. Proceedings of the 17th ICML, Stanford University. 2000"},{"key":"15_CR23","volume-title":"Proceedings of the ACM SIGMOD Conference, 94-105, Seattle, WA","author":"R Agrawal","year":"1998","unstructured":"Agrawal R, Gehrke J, Gunopulos D, Raghavan P: Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the ACM SIGMOD Conference, 94-105, Seattle, WA. 1998"},{"key":"15_CR24","volume-title":"MAFIA: Efficient and scalable subspace clustering for very large data sets","author":"S Goil","year":"1999","unstructured":"Goil S, Nagesh H, Choudhary A: MAFIA: Efficient and scalable subspace clustering for very large data sets. 1999, Technical Report CPDC-TR-9906-010, Northwestern University"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"1805","DOI":"10.1098\/rstb.2005.1730","volume":"360","author":"V Savolainen","year":"2005","unstructured":"Savolainen V, Cowan RS, Vogler AP, Roderick GK, Lane R: Towards writing the encyclopedia of life: an introduction to DNA barcoding. Philos Trans R Soc Lond B Biol Sci. 2005, 360: 1805-1811. 10.1098\/rstb.2005.1730.","journal-title":"Philos Trans R Soc Lond B Biol Sci"},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1080\/10635150500354886","volume":"54","author":"PD Hebert","year":"2005","unstructured":"Hebert PD, Gregory TR: The promise of DNA barcoding for taxonomy. Syst Biol. 2005, 54: 852-859. 10.1080\/10635150500354886.","journal-title":"Syst Biol"},{"issue":"8","key":"15_CR27","doi-asserted-by":"publisher","first-page":"2995","DOI":"10.1128\/JCM.00681-10","volume":"48","author":"PS Conville","year":"2010","unstructured":"Conville PS, Murray PR, Zelazny AM: Evaluation of the Integrated Database Network System (IDNS) SmartGene software for analysis of 16S rRNA gene sequences for identification of Nocardia species. J Clin Microbiol. 2010, 48 (8): 2995-2998. 10.1128\/JCM.00681-10.","journal-title":"J Clin Microbiol"},{"key":"15_CR28","volume-title":"PLoS ONE","author":"M Helal","year":"2011","unstructured":"Helal M, Kong F, Chen SCA, Bain M, Christen R, Sintchenko V: Defining reference sequences for Nocardia species by similarity and clustering analyses of 16S rRNA gene sequence data. PLoS ONE. 2011, (Accepted 12 March 2011)"},{"issue":"9","key":"15_CR29","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1093\/bioinformatics\/17.9.763","volume":"17","author":"KY Yeung","year":"2001","unstructured":"Yeung KY, Ruzzo WL: An empirical study of Principal Component Analysis for clustering gene expression data. Bioinformatics. 2001, 17 (9): 763-774. 10.1093\/bioinformatics\/17.9.763.","journal-title":"Bioinformatics"},{"issue":"1","key":"15_CR30","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1038\/nmeth976","volume":"4","author":"AC McHardy","year":"2007","unstructured":"McHardy AC, Mart\u00edn HG, Tsirigos A, Hugenholtz P, Rigoutsos I: Accurate phylogenetic classification of variable-length DNA fragments. Nature Meth. 2007, 4 (1): 63-72. 10.1038\/nmeth976.","journal-title":"Nature Meth"},{"issue":"6","key":"15_CR31","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/S0168-9525(00)02024-2","volume":"16","author":"P Rice","year":"2000","unstructured":"Rice P, Longden I, Bleasby A: EMBOSS: The European Molecular Biology Open Software Suite. Trends Genetics. 2000, 16 (6): 276-277. 10.1016\/S0168-9525(00)02024-2.","journal-title":"Trends Genetics"},{"key":"15_CR32","first-page":"164","volume":"5","author":"J Felsenstein","year":"1989","unstructured":"Felsenstein J: PHYLIP - Phylogeny Inference Package (Version 3.2). Cladistics. 1989, 5: 164-6.","journal-title":"Cladistics"},{"key":"15_CR33","volume-title":"MATLAB: An introduction with applications","author":"A Gilat","year":"2004","unstructured":"Gilat A: MATLAB: An introduction with applications. 2004, John Wiley & Sons, 2","edition":"2"},{"issue":"4","key":"15_CR34","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1109\/tcbb.2007.1053","volume":"4","author":"P Agius","year":"2007","unstructured":"Agius P, Kreiswirth BN, Naidich S, Bennett KP: Typing Staphylococcus aureus using the spa gene and novel distance measures. IEE\/ACM Trans Comput Biol Bioinform. 2007, 4 (4): 693-704.","journal-title":"IEE\/ACM Trans Comput Biol Bioinform"},{"key":"15_CR35","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1128\/JB.01202-08","volume":"191","author":"M Deloger","year":"2009","unstructured":"Deloger M, El Karoui M, Petit M-A: A genomic distance based on MUM indicates discontinuity between most bacterial species and genera. J Bacteriol. 2009, 191: 91-99. 10.1128\/JB.01202-08.","journal-title":"J Bacteriol"},{"key":"15_CR36","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-78839-3_3","volume":"4955","author":"S Chatterji","year":"2008","unstructured":"Chatterji S, Yamazaki I, Bai Z, Eisen JA: CompostBin: A DNA composition-based algorithm for binning environmental shortgun reads. Research in Computational Molecular Biology\/Lecture Notes in Computer Science. 2008, 4955: 17-28. 10.1007\/978-3-540-78839-3_3.","journal-title":"Research in Computational Molecular Biology\/Lecture Notes in Computer Science"},{"issue":"1","key":"15_CR37","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1038\/nmeth976","volume":"4","author":"AC McHardy","year":"2007","unstructured":"McHardy AC, Martin HG, Tsirigos A, Hugenholtz , Rigoutsos I: Accurate phylogenetic classification of variable-length DNA fragments. Nat Methods. 2007, 4 (1): 63-72. 10.1038\/nmeth976.","journal-title":"Nat Methods"},{"issue":"Suppl 1","key":"15_CR38","doi-asserted-by":"publisher","first-page":"D46","DOI":"10.1093\/nar\/gkp1024","volume":"38","author":"DA Benson","year":"2010","unstructured":"Benson DA, Karsch-Mizrachi I, Lipman DJ, Ostell J, Sayers EW: GenBank. Nucl Acids Res. 2010, 38 (Suppl 1): D46-51.","journal-title":"Nucl Acids Res"},{"issue":"2","key":"15_CR39","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1128\/JCM.01761-09","volume":"48","author":"M Xiao","year":"2010","unstructured":"Xiao M, Kong F, Sorrell TC, Cao Y, Lee OC, Liu Y, Sintchenko V, Chen SCA: Identification of pathogenic Nocardia species by reverse line blot hybridization targeting the 16S rDNA and 16S-23S rDNA spacer regions. J Clin Microbiol. 2010, 48 (2): 503-511. 10.1128\/JCM.01761-09.","journal-title":"J Clin Microbiol"},{"key":"15_CR40","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1099\/00207713-47-2-590","volume":"47","author":"JP Euzeby","year":"1997","unstructured":"Euzeby JP: List of bacterial names with standing in nomenclature. Int J Syst Bacteriol. 1997, 47: 590-592. 10.1099\/00207713-47-2-590. [http:\/\/www.bacterio.cict.fr\/]","journal-title":"Int J Syst Bacteriol"},{"issue":"10","key":"15_CR41","doi-asserted-by":"publisher","first-page":"3192","DOI":"10.1128\/JCM.00628-08","volume":"46","author":"JM Bible","year":"2008","unstructured":"Bible JM, Iturriza-Gomara M, Megson B, Brown D, Pantelidis P, Earl P, Bendig J, Tong CYW: Molecular epidemiology of human enterovirus 71 in the United Kingdom from 1998 to 2006. J Clin Microbiol. 2008, 46 (10): 3192-3200. 10.1128\/JCM.00628-08.","journal-title":"J Clin Microbiol"}],"container-title":["Microbial Informatics and Experimentation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/2042-5783-2-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:25:20Z","timestamp":1630520720000},"score":1,"resource":{"primary":{"URL":"https:\/\/microbialinformaticsj.biomedcentral.com\/articles\/10.1186\/2042-5783-2-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,26]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1186\/2042-5783-2-2","relation":{},"ISSN":["2042-5783"],"issn-type":[{"value":"2042-5783","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,26]]},"assertion":[{"value":"5 May 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}