{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T04:10:10Z","timestamp":1675311010099},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Stem cell differentiation is largely guided by master transcriptional regulators, but it also depends on the expression of other types of genes, such as cell cycle genes, signaling genes, metabolic genes, trafficking genes, etc. Traditional approaches to understanding gene expression patterns across multiple conditions, such as principal components analysis or K-means clustering, can group cell types based on gene expression, but they do so without knowledge of the differentiation hierarchy. Hierarchical clustering can organize cell types into a tree, but in general this tree is different from the differentiation hierarchy itself.<\/jats:p>\n               <jats:p>Methods: Given the differentiation hierarchy and gene expression data at each node, we construct a weighted Euclidean distance metric such that the minimum spanning tree with respect to that metric is precisely the given differentiation hierarchy. We provide a set of linear constraints that are provably sufficient for the desired construction and a linear programming approach to identify sparse sets of weights, effectively identifying genes that are most relevant for discriminating different parts of the tree.<\/jats:p>\n               <jats:p>Results: We apply our method to microarray gene expression data describing 38 cell types in the hematopoiesis hierarchy, constructing a weighted Euclidean metric that uses just 175 genes. However, we find that there are many alternative sets of weights that satisfy the linear constraints. Thus, in the style of random-forest training, we also construct metrics based on random subsets of the genes and compare them to the metric of 175 genes. We then report on the selected genes and their biological functions. Our approach offers a new way to identify genes that may have important roles in stem cell differentiation.<\/jats:p>\n               <jats:p>Contact: \u00a0tperkins@ohri.ca<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv192","type":"journal-article","created":{"date-parts":[[2015,4,7]],"date-time":"2015-04-07T00:02:55Z","timestamp":1428364975000},"page":"2676-2682","source":"Crossref","is-referenced-by-count":0,"title":["Gene selection for the reconstruction of stem cell differentiation trees: a linear programming approach"],"prefix":"10.1093","volume":"31","author":[{"given":"Mohamed A.","family":"Ghadie","sequence":"first","affiliation":[{"name":"1 School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada,"},{"name":"2 Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario K1H 8L6, Canada and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathalie","family":"Japkowicz","sequence":"additional","affiliation":[{"name":"1 School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodore J.","family":"Perkins","sequence":"additional","affiliation":[{"name":"1 School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada,"},{"name":"2 Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario K1H 8L6, Canada and"},{"name":"3 Department of Biochemistry, Microbiology and Immunology, University of Ottawa, 451 Smyth Road, Ottawa, ON K1H 8M5, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,4,5]]},"reference":[{"key":"2023020202200651900_btv192-B1","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1634\/stemcells.2005-0332","article-title":"Defining a developmental path to neural fate by global expression profiling of mouse embryonic stem cells and adult neural stem\/progenitor cells","volume":"24","author":"Aiba","year":"2006","journal-title":"Stem Cells"},{"key":"2023020202200651900_btv192-B2","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1093\/dnares\/dsn035","article-title":"Defining developmental potency and cell lineage trajectories by expression profiling of differentiating mouse embryonic stem cells","volume":"16","author":"Aiba","year":"2009","journal-title":"DNA Res."},{"key":"2023020202200651900_btv192-B3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023020202200651900_btv192-B4","author":"Berkelaar","year":"2007"},{"key":"2023020202200651900_btv192-B5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Mach. Learn."},{"key":"2023020202200651900_btv192-B7","first-page":"451","article-title":"Metric learning by collapsing classes","volume":"18","author":"Globerson","year":"2005","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"2023020202200651900_btv192-B8","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1038\/nprot.2008.211","article-title":"Systematic and integrative analysis of large gene lists using DAVID bioinformatics resources","volume":"4","author":"Huang","year":"2009","journal-title":"Nat. Protoc."},{"key":"2023020202200651900_btv192-B9","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1016\/j.ydbio.2011.02.013","article-title":"Maximum parsimony analysis of gene expression profiles permits the reconstruction of developmental cell lineage trees","volume":"353","author":"Joshi","year":"2011","journal-title":"Dev. Biol."},{"key":"2023020202200651900_btv192-B10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1093\/nar\/28.1.27","article-title":"KEGG: Kyoto encyclopedia of genes and genomes","volume":"28","author":"Kanehisa","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023020202200651900_btv192-B11","doi-asserted-by":"crossref","first-page":"6508","DOI":"10.1073\/pnas.0401136101","article-title":"Lineage specificity of gene expression patterns","volume":"101","author":"Kluger","year":"2004","journal-title":"Proc Natl Acad Sci USA."},{"key":"2023020202200651900_btv192-B12","article-title":"Learning with idealized kernels","author":"Kwok","year":"2003"},{"key":"2023020202200651900_btv192-B13","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1016\/j.cell.2008.01.038","article-title":"Stem cells and niches: mechanisms that promote stem cell maintenance throughout life","volume":"132","author":"Morrison","year":"2008","journal-title":"Cell"},{"key":"2023020202200651900_btv192-B14","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.cell.2011.01.004","article-title":"Densely interconnected transcriptional circuits control cell states in human hematopoiesis","volume":"144","author":"Novershtern","year":"2011","journal-title":"Cell"},{"key":"2023020202200651900_btv192-B15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1038\/35102167","article-title":"Stem cells, cancer, and cancer stem cells","volume":"414","author":"Reya","year":"2001","journal-title":"Nature"},{"key":"2023020202200651900_btv192-B16","article-title":"Distance metric learning for large margin nearest neighbor classification","volume":"18","author":"Weinberger","year":"2006","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"2023020202200651900_btv192-B17","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.1145\/1390156.1390302","article-title":"Fast solvers and efficient implementations for distance metric learning","volume-title":"Proceedings of the 25th International Conference on Machine Learning","author":"Weinberger","year":"2008"},{"key":"2023020202200651900_btv192-B18","first-page":"521","article-title":"Distance metric learning with application to clustering with side-information","volume":"15","author":"Xing","year":"2003","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2023020202200651900_btv192-B19","volume-title":"Distance Metric Learning: A Comprehensive Survey","author":"Yang","year":"2006"},{"key":"2023020202200651900_btv192-B20","first-page":"1","article-title":"Distance metric learning with eigenvalue optimization","volume":"13","author":"Ying","year":"2012","journal-title":"J. Mach. Learn.Res."},{"key":"2023020202200651900_btv192-B21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jim.2006.11.001","article-title":"CD molecules2006\u2014human cell differentiation molecules","volume":"319","author":"Zola","year":"2007","journal-title":"J. Immunol. Methods"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2676\/49034643\/bioinformatics_31_16_2676.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/16\/2676\/49034643\/bioinformatics_31_16_2676.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T03:44:01Z","timestamp":1675309441000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/16\/2676\/320841"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,5]]},"references-count":20,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2015,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv192","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,8,15]]},"published":{"date-parts":[[2015,4,5]]}}}