{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:58:03Z","timestamp":1778083083724,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Multi-dimensional scaling (MDS) is aimed to represent high dimensional data in a low dimensional space with preservation of the similarities between data points. This reduction in dimensionality is crucial for analyzing and revealing the genuine structure hidden in the data. For noisy data, dimension reduction can effectively reduce the effect of noise on the embedded structure. For large data set, dimension reduction can effectively reduce information retrieval complexity. Thus, MDS techniques are used in many applications of data mining and gene network research. However, although there have been a number of studies that applied MDS techniques to genomics research, the number of analyzed data points was restricted by the high computational complexity of MDS. In general, a non-metric MDS method is faster than a metric MDS, but it does not preserve the true relationships. The computational complexity of most metric MDS methods is over <jats:italic>O(N<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              <jats:italic>)<\/jats:italic>, so that it is difficult to process a data set of a large number of genes <jats:italic>N<\/jats:italic>, such as in the case of whole genome microarray data.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We developed a new rapid metric MDS method with a low computational complexity, making metric MDS applicable for large data sets. Computer simulation showed that the new method of split-and-combine MDS (SC-MDS) is fast, accurate and efficient. Our empirical studies using microarray data on the yeast cell cycle showed that the performance of K-means in the reduced dimensional space is similar to or slightly better than that of K-means in the original space, but about three times faster to obtain the clustering results. Our clustering results using SC-MDS are more stable than those in the original space. Hence, the proposed SC-MDS is useful for analyzing whole genome data.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Our new method reduces the computational complexity from <jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic>\n              <jats:sup>3<\/jats:sup>) to <jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic>) when the dimension of the feature space is far less than the number of genes <jats:italic>N<\/jats:italic>, and it successfully reconstructs the low dimensional representation as does the classical MDS. Its performance depends on the grouping method and the minimal number of the intersection points between groups. Feasible methods for grouping methods are suggested; each group must contain both neighboring and far apart data points. Our method can represent high dimensional large data set in a low dimensional space not only efficiently but also effectively.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-179","type":"journal-article","created":{"date-parts":[[2008,4,4]],"date-time":"2008-04-04T18:13:04Z","timestamp":1207332784000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":90,"title":["Multidimensional scaling for large genomic data sets"],"prefix":"10.1186","volume":"9","author":[{"given":"Jengnan","family":"Tzeng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry Horng-Shing","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen-Hsiung","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,4]]},"reference":[{"key":"2164_CR1","volume-title":"Multivariate Analysis","author":"KV Mardia","year":"1979","unstructured":"Mardia KV, Kent JT, Bibby JM: Multivariate Analysis. Academia Press; 1979."},{"issue":"5500","key":"2164_CR2","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum JB, Vin de Silva , Langford JC: A global geometric framework for nonlinear dimensionality reduction. Science 2000, 290(5500):2319\u20132323.","journal-title":"Science"},{"key":"2164_CR3","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1057\/palgrave.ivs.9500040","volume":"2","author":"A Morrison","year":"2003","unstructured":"Morrison A, Ross G, Chalmers M: Fast multidimensional scaling through sampling, springs and interpolation. Information Visualization 2003, 2: 68\u201377.","journal-title":"Information Visualization"},{"issue":"6","key":"2164_CR4","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1093\/bioinformatics\/bti067","volume":"21","author":"Y-h Taguchi","year":"2005","unstructured":"Taguchi Y-h, Oono Y: Relational patterns of gene expression via non-metric multidimensional scaling analysis. Bioinformatics 2005, 21(6):730\u2013740.","journal-title":"Bioinformatics"},{"issue":"16","key":"2164_CR5","doi-asserted-by":"publisher","first-page":"2266","DOI":"10.1101\/gad.1450606","volume":"20","author":"T Pramila","year":"2006","unstructured":"Pramila T, Wu W, Miles S, Noble WS, Breeden LL: The Forkhead transcription factor Hcm1 regulates chromosome segregation genes and fills the S-phase gap in the transcriptional circuitry of the cell cycle. Genes Dev 2006, 20(16):2266\u20132278.","journal-title":"Genes Dev"},{"key":"2164_CR6","volume-title":"Modern Multidimensional Scaling: Theory and Applications (Springer Series in Statistics)","author":"I Borg","year":"1996","unstructured":"Borg I, Groenen P: Modern Multidimensional Scaling: Theory and Applications (Springer Series in Statistics). New York: Springer-Verlag; 1996."},{"key":"2164_CR7","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF02288916","volume":"17","author":"WS Torgerson","year":"1952","unstructured":"Torgerson WS: Multidimensional scaling: I. theory and method. Psychometrika 1952, 17: 401\u2013419.","journal-title":"Psychometrika"},{"key":"2164_CR8","first-page":"127","volume-title":"Proceedings of the 7th conference on Visualization","author":"M Chalmers","year":"1996","unstructured":"Chalmers M: A linear iteration time layout algorithm for visualizing high-dimensional data. Proceedings of the 7th conference on Visualization 1996, 127-ff."},{"key":"2164_CR9","first-page":"149","volume":"42","author":"P Eades","year":"1984","unstructured":"Eades P: A heuristic for graph drawing. Congressus Numerantium 1984, 42: 149\u2013160.","journal-title":"Congressus Numerantium"},{"key":"2164_CR10","volume-title":"Journal of Computational and Graphical Statistics","author":"A Buja","year":"2001","unstructured":"Buja A, Swayne DF, Littman M, Dean N, Hofmann H: XGvis: Interactive data visualization with multidimensional scaling. Journal of Computational and Graphical Statistics 2001."},{"key":"2164_CR11","volume-title":"Encyclopedia of Cognitive Science","author":"M Steyvers","year":"2002","unstructured":"Steyvers M: Multidimensional Scaling. In Encyclopedia of Cognitive Science. London: Nature Publishing Group; 2002."},{"key":"2164_CR12","first-page":"152","volume-title":"Proc IEEE Information Visualization (InfoVis'02)","author":"A Morrison","year":"2002","unstructured":"Morrison A, Ross G, Chalmers M: A hybrid layout algorithm for sub-quadratic multidimensional scaling. Proc IEEE Information Visualization (InfoVis'02) 2002, 152\u2013158."},{"issue":"6","key":"2164_CR13","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1093\/bioinformatics\/17.6.520","volume":"17","author":"O Troyanskaya","year":"2001","unstructured":"Troyanskaya O, Cantor M, Sherlock G, Brown P, Hastie T, Tibshirani R, Botstein D, Altman RB: Missing value estimation methods for DNA microarrays. Bioinformatics 2001, 17(6):520\u2013525.","journal-title":"Bioinformatics"},{"key":"2164_CR14","volume-title":"10th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"T Sherwood","year":"2002","unstructured":"Sherwood T, Perelman E, Hamerly G, Calder B: Automatically characterizing large scale program behavior. 10th International Conference on Architectural Support for Programming Languages and Operating Systems 2002."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-179.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:18:19Z","timestamp":1630466299000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,4]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2164"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-179","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,4]]},"assertion":[{"value":"21 June 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"179"}}