Biomedical Informatics 214 (also listed as Computer Science 274) Representations and Algorithms for Computational Molecular Biology Spring 2007

Programming Project 2

Due electronically by 5:00pm, Monday April 30, 2007

Note that programming projects should be completed individually. You may discuss algorithms with others, but the coding should be done alone.
Remember to consult the FAQ periodically as it will be updated with answers to common questions.

Contents:

1. Introduction
2. K-nearest neighbors
3. K-means
4. Submission contents
5. Submission instructions

Introduction

In this project you will be implementing both K-nearest neighbor (a supervised machine learning algorithm) and K-means (an unsupervised machine learning algorithm) to analyze microarray data.

I. K nearest neighbors

Methodology:

The basic idea is the following: given an expression vector for an unclassified patient, find the K "closest" expression vectors from the classified patients and let them vote on the classification for the query patient. If some p percent or more of the K neighbors are ALL patients then classify the unknown patient as ALL, otherwise classify it as AML. Your function should take in the positive training set (ALL patient data), a negative training set (AML patient data), a positive integer for K, and a value between 0 and 1 for p. It should return a vector of predictions -- one prediction for each patient in the test set. Use Euclidean distance as your distance metric.

Deliverables:

You will need to submit a script or source for an executable called "knn" (obviously the extension will vary by language) to perform k-nearest neighbors classification with the two  input file names, k and p (in that order) as command line arguments.  For example for the leukemia dataset the command line arguments should read: "knn ALL.dat AML.dat k p".  Output should be to both <stdout> and a file called "knn.out" exactly as below, where 10 and .75 are used for k and p respectively (other #'s are made up):

k: 10
p: .75
accuracy: .68
sensitivity: .85
specificity: .9

Cross validation:

To assess the accuracy of a classifier, we typically use an approach known as n-fold cross-validation. In this strategy we:

1. Divide the training set into n groups randomly (Divide the positive set into n groups and the negative set into n groups and then combine them so that each of the final n groups have equal proportions of ALL and AML patients)
2. We use one of the n subsets as our test set and the other n-1 as our training set. 
3. We repeat step (2) n times. We assess the test accuracy (sensitivity, specificity, or a combination of the two) by averaging over all the runs. In your runs you should use 4-fold cross-validation in your computations of accuracy.

Where TP = number of true positives, FN = number of false negatives, FP = the number of false positives, and TN = the number of true negatives in the test set.    

Data:

The dataset you will use for classification consists of microarray expression data for 72 leukemia patients. Experiments are described in detail in the paper:

T.R. Golub, D.K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J.P. Mesirov, H. Coller, M. Loh, J.R. Downing, M.A. Caligiuri, C.D. Bloomfield, and E.S. Lander, D. Molecular Classification of Cancer: Class Discovery and Class Prediction by Gene Expression. Science. 99:531-537.

The expression data for the 28 AML patients can be found in the tab delimited file AML.dat. Each column in the file represents a different AML patient. Each of the 7129 rows correspond to a different gene. The expression data for the 44 ALL patients can be found in  ALL.dat. The genes in this data set are in the same order as those in the AML data set. A description of the 7129 genes can be found in human_genes.txt.

• Your command line arguments for the executables of KNN should be something like knn ALL.dat AML.dat k p
  where k is the number of neighbors that have a "vote", and p is the minimum fraction of "votes" needed in order to classify a sample as positive.
  
  
• Clarification of n-fold cross validation:
  In the case when n=4:
  Divide the data into 4 equally (or as close to equally) sized sets. Make sure that the ratio of ALL to AML patients are the same in each set. You can do this by splitting the ALL and AML data into 4 sets separately and then combining them. Now take three (n-1) of the four subsets and combine them to make the training set. Next run KNN on this training set using the remaining 1 (out of the 4) set to test the classification.
  We want to repeat this four times. Each time one of the 4 is left out as the test set, and the remaining 3 are used as the training set. A diagram can be found here.
  
  Note: You only need to randomize and split the data once. Once the data is split you alternate which single subset is used as the test set.

• When partitioning data for the cross-validation step of KNN you cannot use a deterministic partition, but rather must divide the data randomly. Frequently you can get artifacts due to the ordering of the data. For example, imagine you are doing KNN on the yeast data to try to classify ribosomal genes. If you deterministically devided the data into 4 then all of the ribosomes would be in the same test set which would drastically affect your results.

II. K-means

Introduction:

Analysis of microarray data can be on the experiment level (cluster/classify experiments), at the gene level (cluster/classify genes), or both (see biclustering if interested).  In part I you performed k-nearest neighbors to classify microarray experiments based on gene expression. In this section, you will perform K-means clustering on the genes, clustering together genes who have similar expression profiles over a multitude of experimental conditions. 

K-means clustering:

Implement the K-means clustering method discussed in class. The basic idea of K-means clustering is the following:

• Choose an initial partition of the data into K clusters (the centers can be picked at random, or specified by the user). 
• For each data point, assign it to a cluster such that the euclidean distance from the data point to the center is minimal. 
• For each cluster, recalculate the centers based on all the data points that belong to that cluster. 
• Iterate until converge (no data points change cluster) or after a certain number of interactions (eg. 50).

The data consists of microarrays spanning 79 experiments, including measurements of expression taken after environmental changes were imposed on the yeast. For example, some of these conditions were starvation (causing the yeast to form spores), changing the sugar supply (causing the yeast to ferment rather than respire), and synchronizing the cells to force them to pass through the stages of cell division at the same time. The experiments are described in detail in the paper:

Eisen, M.B., Spellman, P.T., Brown, P.O., Botstein, D. Cluster analysis and display of genome-wide expression patterns. PNAS. 95:14863-14868.

You will need to submit a script or source for an executable called "kmeans" (obviously the extension will vary by language) to perform k-means clustering with the number of clusters (K), filename for the tab delimited data file, the maximum number of iterations allowed and an optional 4th parameter for reading cetroids from a file.  If the filename for the centroids is not specified then the K initial centroids should be generated randomly. The initial centroid file should contain a Kx79 matrix in tab delimited form.  Sample centroid input filefor K=3 can be found here (test_centroids.txt).

Output should be writted to a file called "kmeans.out".   The output should contain the cluster assignment for each gene by index (i.e the first gene in the list is gene #1 etc...):

For example (K=3):
1    2
2    1
3    3
4    1
5    2
6    1
7    1
8    2
9    1

where the first column is the gene number and the second column designates a cluster assignment (the numbering of the clusters is arbitrary as long as two genes in the same cluster have the same cluster number).

• In this section we ask you to specify the maximum number of iterations for k-means in the command line.
  This argument specifies the maximum number of iterations we allow before cutting off if convergence is not acheived. It is useful for testing (and more importantly for us grading) purposes. Also it allows you to get "pretty good" results in cases when it is taking a long time to converge. For this project we generally want it set pretty high (I will test it on 50 iterations).
  
  NOTE: Do not rely on the maximum iteration parameter to stop the program. If k-means converges before the maximum number of itereations is reached then it should stop then.
  
  
• Your command line arguments for the executables of kmeans should be something like: kmeans k yeast.dat max.it testCentroids.txt
  where k is the number of centroids, yeast.dat is the tab delimited file containing expression data for 2467 genes in 79 experiments, max.it is the maximum number of iterations allowed, and testCentroids.txt is an optional parameter specifying a file from which intital centroids should be read. If this filename is not present then centroids should be generated randomly.

What you will need to submit:

1. Source code for knn and kmeans.
   • We expect well-commented code, especially if you want partial credit for "almost working" code.
   • Include makefiles if necessary.
   • If you have binary executables, please delete them before submitting.

2. A README file. Please call it README.txt This should include three sections.
   • Your name and SUNet ID
   • Language used and instructions on how to run your programs
   • Pseudocode description of the algorithms (approx. one page or less each). We will use this as a primary way to debug the conceptual basis for your code, especially for partial credit.

3. A file called project2_quiz.pdf, containing answers to Project 2 Quiz. This file should be submitted as a pdf file called project2_quiz.pdf

Submission instructions

Log in to an elaine machine:

ssh sunetid@elaine.stanford.edu

Place all of your relevant files (the three sections outlined above) into one directory. E.g.

~/biomedin214/p2/submit

cd into your submit folder.

cd ~/biomedin214/p2/submit

Run the class submission script:

/usr/class/biomedin214/bin/submit p2

You may submit multiple times; simply re-run the script. Each new submission overwrites the previous submission. Your submission date will be the final submission received, and late days will be charged accordingly.