title: Gene selection for the reconstruction of stem cell differentiation trees: a linear programming approach.
abstract: BACKGROUND
  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.
  
  
  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.
  
  
  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.
  
  
  BACKGROUND
  tperkins@ohri.ca
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada, Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario K1H 8L6, Canada and.
authors.forename: Mohamed A
authors.initials: MA
authors.lastname: Ghadie
authors.affiliation: School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada.
authors.forename: Nathalie
authors.initials: N
authors.lastname: Japkowicz
authors.affiliation: School of Electrical Engineering and Computer Science, University of Ottawa, 75 Laurier Avenue East, Ottawa, ON K1N 6N5, Canada, Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario K1H 8L6, Canada and Department of Biochemistry, Microbiology and Immunology, University of Ottawa, 451 Smyth Road, Ottawa, ON K1H 8M5, Canada.
authors.forename: Theodore J
authors.initials: TJ
authors.lastname: Perkins
mesh_terms: D001773:Blood Cells / Q000166:cytology; D002454:Cell Differentiation / Q000235:genetics*; D016000:Cluster Analysis; D005786:Gene Expression Regulation; D005796:Genes; D006801:Humans; D011382:Programming, Linear; D013234:Stem Cells / Q000166:cytology*