Jason Knight

What does our DNA look like?

2011-06-24T17:03:00.000-05:00

Everyone has seen the DNA double helix (if not click here right now), but what does your DNA look like as an image?

Specifically, I was daydreaming today when I thought: what if someone took one of the sequenced human genomes out there and converted all the letters into corresponding colors for the pixels of an image?

I decided that that someone was going to be me!

And a few minutes later with somewhere north of 25 google searches (where do I download the human genome? How do I remove newlines and capitalize letters with awk? How can I write PNGs with Haskell? What color code is a 32bit RGBA PNG in its header? etc...) I had my answer:

Now, a few caveats: This is only a portion of the Y chromosome of the 19th human sequenced. It really doesn't look like much does it? But it was a fun exercise for the 30 minutes or so before I headed home for the weekend.

The code (almost all of which came from this PNG example) can be found here. It is very ugly and does not use Haskell as it was meant to be used. But it gets the job done!

Please let me know if you have any suggestions as to making the image prettier/more informative. Perhaps I should indicate the location of TATA boxes or Poly-A tails etc... Maybe I'll find some time to do it too!

Just imagine that most of that is inside of us (the guys anyways, sorry ladies!), inside of every cell in our bodies in fact. Kinda neat if you ask me.

Our New ChromeOS Notebook - First Impressions

2010-12-16T23:17:00.000-06:00

Well, it is getting 'late' here, so I must keep this short, but to see pictures of what the CR-48 laptop looks like, I would highly recommend the below reviews I found. They also go into more depth of all the features and everything. But I will leave you with some quick first impressions.

It has occurred to me that this computer is *perfect* for people like Emily. It basically strips out all the unnecessary cruft of the OS that has been accumulating for decades, and puts you right onto the internet as quick as possible. The simplicity of this experience is very refreshing, and it takes some getting used to, but after browsing the Chrome App Store for a bit, and playing some games with Emily there, I realized how ready we are for this transition-to-the-cloud to occur.

The hardware is really great (you'll read opposite opinions elsewhere), and it really is the perfect 12" form factor that is slim and light enough to carry around with you, but big enough that you don't feel cramped while typing or browsing. The sleep-wake behavior is beautiful, it sleeps and wakes so effortlessly that you wonder why this has never been perfected before (except on a few Macbooks that I've seen people around me use).

It is a little slow, but because the browser is basically running on the metal, you don't really notice it except on occasion. Although I have not tried youtube, the html5 video player on vimeo seemed to work just fine for me.

One really promising feature is when you alt+tab to different browser windows, the effect is obviously hardware accelerated and liquid smooth, which makes me pine for the days when Chrome gets hardware accelerated rendering (as then all scrolling should theoretically be that smooth).

So Emily and I are going to share the cr48 (although we need to come up with a cuter name for it), as I think it is an even better fit for her than it is for me (I've found that you can Ctrl+Alt+T to open a limited shell that I can ssh from, but that's kinda besides the point of a notebook like this).

I'm excited to try the battery life out some, and see how the free 3G performance is from Verizon.

Here's those reviews:

Optimizing Python + Numpy Code

2010-04-04T21:48:00.000-05:00

So I decided to learn Cython, and in doing so, I found an interesting post comparing Matlab speed to Numpy + Python and Numpy + Cython. Obviously I was intrigued, and with the available code, pasted into vim I was off and running!

The first thing to do is the first step in ALL optimization workflows: profiling! Using the wonderful cProfile.run('GMMGaussianMC(100000)','prof.dat') we can glean the following: (output pasted here for readability).

Hmmm.. 32 seconds (out of 60) in numpy.linalg.solve
Only 10 seconds is spent 'in' GMMGaussian (and 3 in GMMGaussianMC), so the bulk is in Numpy

This explains why Tim's Cython conversion did not net any gain (it's all numpy bound). Thus while chewing on the numpy problem, I started implementing some simple (but in retrospect, probably minor) common python + numpy optimizations: vectorizing code by pulling it out of the inner for loop. And inlining the function call (I'd be curious to see how much this helped, as it is a rather ugly change in general).

This took us down from 30 seconds to about 22 seconds, not bad, but not great either.

Now, for the linear algebra. It appears that a great deal of our time is spent in the numpy.linalg.solve function, why is this? And after a bit of searching I found this insightful mailing list post (see towards the bottom). It appears that MATLAB does a lot of heuristics in order to use the most efficient way of solving a linear system, whereas numpy takes the easy out approach by calling the generic LAPACK solver (DGESV for anyone interested). After rejecting the idea of compiling a faster LAPACK because it would require rebuilding Numpy, I decided to look more closely at the linear algebra at use in the code.

Sure enough, I found that we were dealing with purely diagonal matrices which makes the prospect of simply inverting and multiplying possible. BAM!!! This takes us down to 8 seconds, which is comparable to the MATLAB script.

Profiling now we can see that everything is either in the GMMGaussianMC function, or quick numpy functions like randn, dot, inner, etc... There is not much we can do about this to my knowledge, so we are now done! (link to final code)

Now time to go learn about the theory behind this algorithm...

P.S. Sorry about the poor writing quality in this post, I'm trying to talk and write at the same time, and the result is a poor mess of both :)

Support Vector Machines - An Introduction

2010-04-02T00:05:00.000-05:00

This one goes out to Bryan to explain what a support vector machine is, but first I must cover a little bit of background information first.

Pattern Recognition
Let's say that we are a farmer trying to decide if our crops are going to be healthy this season, or ridden with locusts. We know that the chance of locust infection is heavily dependent on a lot of factors such as the length of the winter, the previous harvest size, and the last season's locust amounts. Ideally we would like to feed this data, the 'feature vector', into a black box that would output an accurate prediction for the presence or absence of locusts this year.

Being a mathematically trained farmer, we would know that there exists toolsets to do just that, so we would root around in our filing cabinets pulling up data of locust infections from years past and the corresponding weather patterns and harvests to makeup a training data set.

Now for a bit of definitions, a classification rule is a mathematical function that takes a set of training data and produces a classifier. A classifier is a function that maps a single feature vector, or sample point, to a label. These labels can be yes/no, locust/no locust, healthy/unhealthy, or even consist of multiple classes.

As a farmer, we will take our training data, use a classification rule in order to produce a classifier, and then input this year's parameters into the classifier in order to obtain a prediction for this years locust population.

Now, a small aside, why do we even bother with this in the first place? Usually the need to automate this process of prediction comes down to speed and complexity. For instance, in a factory where we want to separate tuna from sea bass we may want to classify several hundred fish per second. Or more often the case, the predictions are done in such highly complex scenarios that humans cannot easily handle them intuitively (can you visualize hundred dimensional spaces?).

Which classification rule (thus classifier) we use is a complicated issue, but today we'll talk about support vector machines (SVMs).

Support Vector Machines
The essence of SVMs is simple, take the training data, and divide the data into two (for a two class classifier) using a straight line. Or in three dimensions, use a plane, and anything higher, use a hyper plane. The math works out the same, but it is easier to visualize in the 2D line case.

How do we determine where to draw the line? Simply pick the line that creates the largest gap (or margin) between the closest set of opposing points. This can be formalized into an optimization problem, which I won't get into how to solve here, and the resulting hyperplane is used as our classifier. To do so, we simply take the current data point (this year's data) and see if it is on the locust or non-locust side of the (hyper)plane. See the image to the right (credit to Wikimedia) for a nice visual.

Now what if the data overlaps? Then we have to move to nonlinear kernel based SVMs where we map our 'low' dimensional data into a higher dimensional space using a fancy kernel function and try to separate it there.

There are many technicalities and finer points here, but that is the essence of what SVM does.

Note to Bryan, Kevin, and Hope: Now, for hyperspectral imaging, each pixel of a hyperspectral image contains hundreds of values, one for each frequency band, and these are usually taken far enough away from the object of interest, that each pixel represents the combination of several signatures (or endmembers). Thus, an image might be 5 meter resolution and contain the signature for both soil and corn crop, and we wish to extract each of those endmembers from the several hundred values in the pixel. Using SVM to accomplish this leads to SVM endmember extraction. :)

Welcome!

2010-03-31T19:13:00.000-05:00

After Esmaeil showed me how blogger had changed over the years, I decided to implement my personal page here and see how it goes. Let's see if I can stick to updating this thing and making it work.