science help

BIFS614 Data Structure and Algorithms HW4

Due on 04/20/2014

Microarray data analysis (50 points)

One of the many challenges in diagnosing and treating cancers is that cancers which appear

clinically similar can be genetically heterogeneous. The disparate gene defects can have different

implications for prognosis and treatment of the cancer. You will be dealing with two different

forms of acute leukemia, namely acute myeloid leukemia (AML) and acute lymphoblastic

leukemia (ALL). The two leukemias appear very similar morphologically. However, because the

chemotherapy regimens differ for AML and ALL patients, the ability to distinguish between

them is critical for successful treatment.

You will be analyzing microarray data from experiments based on 38 patients with either AML

or ALL. The microarray experiments were performed by extracting RNA samples from bone

marrow cells of the patients and hybridizing the RNA to a microarray chip. The Microarray data

set is attached (HW4-ALL-AML.txt).

In order to analyze the data via clustering, you can download and install two programs, Cluster

3.0 and Java TreeView, which are freely available via the Internet.

http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/software.htm#ctv

The first program, Cluster 3.0, actually clusters the data, while the program, TreeView, is used

for viewing the clustering results.

1. If you cluster with a kMeans algorithm, and then repeat the kMeans clustering with the same parameters, do the results change? If you cluster with a hierarchical algorithm, and

then repeat the hierarchical clustering with the same parameters, do the results change?

Why? (HINTS: explain “Why” part based on how kMeans and hierarchical algorithms

work. Make sure that you understand how these two types of clustering algorithms work)

2. Do your clustering results indicate that microarray experiments can be used to distinguish between different forms of acute leukemia? How confident would you be in

diagnoses made on the basis of this small microarray data set?

Requirement: please include a treeview diagram of the hierarchical clustering result.

Evolutional (phylogenetic) tree construction (50 points)

Given the following distance matrix of five sequences A, B, C, D, and E:

3. Construct a phylogenetic tree using the UPGMA approach; 4. Construct a phylogenetic tree using the neighbor joining approach.

Requirement: Report all the partial trees and matrices for the intermediate steps.