The Neon Open Sign

A new craze has swept the retail community.  It’s the neon open sign  and it looks like this:

Even in my quaint neighborhood of Noe Valley in San Francisco, we are inundated with this ubiquitous symbol of openness.  When I see this sign the following thoughts go through my head in this order:

1. Shock  – Wow, another one of these signs (?!)
2. Enlightenment - This business is probably low quality / unoriginal / not trying hard.
3. Confusion - Why would the proprietor want to convey these connotations?
4. Trivia – I guess this establishment is open / closed.

In just a few blocks along 24th street in Noe Valley I counted six of these eyesores.  It is a perfect example of horrible design and poor marketing.  A hand painted open sign is friendlier, unique, conveys personality, and is only a fraction of the cost.  Here is my favorite sign on 24th Street for a shop called ladybug ladybug:

E2K9 update

I love emailing customer service and getting back meaningless form letters.  Trying to get to the bottom of what happened to Evite on New Year’s Eve led to a typical exchange, including once where they did not respond, so I replied again adding a few corporate CC’s,  This is an excellent tactic to getting a response.  Anyway seven emails later I ended up with the following information from a senior CSR:

“This outage was due to unforeseen system difficulties.”  and “Unfortunately,  . . . we cannot provide the specific system issues.”

As you can see from the following screen shot, this contradicts the message that the disruption was due to “planned maintenance.”

Evite was very fortunate that there was not more public fallout from this.

The Adaptive Immune System

This is a continuation of the previous post about the immune system, where now we focus on the lymphatic system.

Humans have a very advanced part of their immune system known as the adaptive immune system, which is only found in jawed mammals.  In this system certain leukocytes, called Antigen-presenting cells (APCs), can bring in another line of defense by notifying T-cells that there is an infection.

How they accomplish this is quite remarkable:  by tearing by apart the internalized pathogen and presenting the pathogen’s antigens on its surface.  Antigens are structures which identify the pathogen and produce a specific immune response in T-cells.  Our APC must now move to our T-cells, which are located in our lymph nodes, and present the antigens to activate them. The APC again uses chemotaxis to traverse through lymph vessels to reach the nodes.  It the presents the antigens attached to a special structure called MHC to “naive” T-cells.

This T cell (blue), one of the immune system’s principal means of defense, identifies the molecular signature of a dendritic cell (gray) at a contact point called the immunological synapse. http://www.lbl.gov/Publications/Currents/Archive/Oct-03-2003.html#head0

T-Cells have special T-Cell Receptors (TCRs), which have constant parts which always bind to MHC, and variable parts which will only bind to specific antigens.  Upon activation some T-cells become “T helper cells” (CD4+) and others become “Cytotoxic T-cells” (CD8+). The CD4+ cause the growth of more CD4+, which will release chemicals which stimulate more white blood cells to the site of the infection.  Cytotoxic cell kill infected cells, as their name implies.  They both return to the site of the infection through chemotaxis.

After the infection is eliminated, the specific antigens which the T-cells bound to will be “remembered” by memory T-cells.  These cells bind only with the previous antigen and so the immune system is more prepared for a recurrence of the same infection.

Clearly I glossed over much, so read more for the real details.  It’s an amazing system all accomplished with molecular machines!

The Common Cold

A few weeks ago had a small cold.  I wondered what was really going on inside my body.  It turns out this is a complicated and fantastic story about the immune system.  First let’s over the high-level events of the common cold:

1. A Rhinovirus infects the upper respiratory system
2. Leukocytes detect the virus
3. Leukocytes initiate inflammation
4. Adaptive immune system is activated
5. The virus is eliminated

Now let’s check these steps out in more detail:

Infection

A virus (usually a rhinovirus) enters your nose and lands on your adenoids (part of your tonsils) the virus binds to the epithelial cells with proteins called cell adhesion molecules.   You can think of it like cellular Velcro, but instead of little plastic hooks they’re made of protein structures which interlock.  This binding changes the structure of the virus’s protein shell (the capsid), which in turn causes myristic acid to be released onto the infected cell.  This acid creates a pore through which the virus can inject its RNA.  Once RNA is within the host cell, it begins replication through RNA transcription.

Detection

The immune system has cells which contain special “pattern recognition receptors” (PRRa) made of protein, which bind with various pathogens including viruses.   Examples of these cells are leukocytes (white blood cells) including macrophages and dendritic cells which both bind with viruses.  If a leukocyte binds with a rhinovirus (or other pathogen) with its PRRs, then it will internalize it in a process called phagocytosis.

Here is an incredible video of another leukocyte called neutrophils chasing down a bacterium and phagoticizing it.  Neutrophils is about 14 microns across, and I believe this video was shot over several hours:

Inflammation

These activated leukocytes respond to the binding of pathogens by release chemicals called cytokines.  These chemicals are one way which cells communicate and organize their efforts.  In the immune system, releasing cytokines, as well as other chemicals, draw more leukocytes to the site of the infection through an amazing process of cellular motion called chemotaxis.   Chemotaxis is basically proteins moving in response to their chemical environment, which causes a cell to propel itself  in a specific direction to reach its chemical goal.  This process escalates the inflammation in a feedback loop of chemotaxis, phagocytosis, and cytokine release.  These released chemicals also cause the familiar symptoms of inflammation: redness, heat, swelling, pain, and loss of function.

In my next post I’ll talking about the adaptive immune system which is pretty incredible.

How Shazam Works

There is a cool service called Shazam, which take a short sample of music, and identifies the song.  There are couple ways to use it, but one of the more convenient is to install their free app onto an iPhone.  Just hit the “tag now” button, hold the phone’s mic up to a speaker, and it will usually identify the song and provide artist information, as well as a link to purchase the album.

What is so remarkable about the service, is that it works on very obscure songs and will do so even with extraneous background noise.  I’ve gotten it to work sitting down in a crowded coffee shop and pizzeria.

So I was curious how it worked, and luckily there is a paper written by one of the developers explaining just that.  Of course they leave out some of the details, but the basic idea is exactly what you would expect:  it relies on fingerprinting music based on the spectrogram.

Here are the basic steps:

1. Before hand, Shazam fingerprints a comprehensive catalog of music, and stores the fingerprints in a database.
2. A user “tags” a song they hear, which fingerprints a 10 second sample of audio.
3. The Shazam app uploads the fingerprint to Shazam’s service, which runs a search for a matching fingerprint in their database.
4. If a match is found, the song info is returned to the user, otherwise an error is returned.

Here’s how the fingerprinting works:

You can think of any piece of music as a time-frequency graph called a spectrogram..  On one axis is time, on another is frequency, and on the 3rd is intensity.  Each point on the graph represents the intensity of a given frequency at a specific point in time. Assuming time is on the x-axis and frequency is on the y-axis, a horizontal line would represent a continuous pure tone and a vertical line would represent an instantaneous burst of white noise.  Here’s one example of how a song might look:

Spectrogram of a song sample with peak intensities marked in red. Wang, Avery Li-Chun. An Industrial-Strength Audio Search Algorithm. Shazam Entertainment, 2003. Fig. 1A,B.

The Shazam algorithm fingerprints a song by generating this 3d graph, and identifying frequencies of “peak intensity.”  For each of these peak points it keeps track of the frequency and the amount of time from the beginning of the track.  Based on the paper’s examples, I’m guessing they find about 3 of these points per second. [Update: A commenter below notes that in his own implementation he needed more like 30 points/sec.]  So an example of a fingerprint  for a 10 seconds sample might be:

Frequency in Hz	Time in seconds
823.44	1.054
1892.31	1.321
712.84	1.703
. . .	. . .
819.71	9.943

Shazam builds their fingerprint catalog out as a hash table, where the key is the frequency.  When Shazam receives a fingerprint like the one above, it uses the first key (in this case 823.44), and it searches for all matching songs.  Their hash table might look like the following:

Frequency in Hz	Time in seconds, song information
823.43	53.352, “Song A” by Artist 1
823.44	34.678, “Song B” by Artist 2
823.45	108.65, “Song C’ by Artist 3
. . .	. . .
1892.31	34.945, “Song B” by Artist 2

[Some extra detail: They do not just mark a single point in the spectrogram, rather they mark a pair of points: the "peak intensity" plus a second "anchor point".  So their key is not just a single frequency, it is a hash of the frequencies of both points.  This leads to less hash collisions which in turn speeds up catalog searching by several orders of magnitude by allowing them to take greater advantage of the table's constant (O(1)) look-up time.  There's many interesting things to say about hashing, but I'm not going to go into them here, so just read around the links in this paragraph if you're interested.]

If a specific song is hit multiple times (based on examples in the paper I think it needs about 1 frequency hit per second), it then checks to see if these frequencies correspond in time.  They actually have a clever way of doing this  They create a 2d plot of frequency hits, on one axis is the time from the beginning of the track those frequencies appear in the song, on the other axis is the time those frequencies appear in the sample.  If there is a temporal relation between the sets of points, then the points will align along a diaganol!  They use another signal processing method to find this line, and if it exists with some certainty, then they label the song a match.

Top graph: Songs and sample have many frequency matches, but they do not align in time, so there is no match. Bottom Graph: frequency matches occur at the same time, so the song and sample are a match. Wang, Avery Li-Chun. An Industrial-Strength Audio Search Algorithm. Shazam Entertainment, 2003. Fig. 2B.

Z2K9 and E2K9

This New Year’s we witnessed 2 catastrophic tech failures:  Zune and Evite.  On New Year’s Eve, Zune 30s all over the world froze.  Microsoft said it was due to “‘a bug in the internal clock driver,” and that affected Zunes would work the following day.  For evite, the site went down on one of the busiest party nights of the year around 6pm EST and did not come up until after the ball dropped.  I, along with possibly millions of others, could not access NYE party information which is only stored on the evite site.  This is particularly bad as evite has more competition than ever, and people are just looking for reasons to switch to something else more web 2.0-ish.

So, some industrious poster tracked down the Zune clock source code.  Here is the bad code, which is called whenever the Zune needs the current date:

year = ORIGINYEAR; /* = 1980 */

while (days > 365)
{
    if (IsLeapYear(year))
    {
        if (days > 366)
        {
            days -= 366;
            year += 1;
        }
    }
    else
    {
        days -= 365;
        year += 1;
    }
}

This method take an argument of “days”, which is the number of days since 1/1/1980.  If days=366 and isLeapYear() is true, then this loop does nothing and will loop forever.  These conditions always occur on the last day of a leap year (e.g 12/31/2008) !  The bottom-line is that when you write a loop, you need to be certain it will terminate.  Having a convoluted assortment of if-statements it not a good way to accomplish this.

So we know the Zune crash was caused by a date bug, but the evite error has not been explained.  I donned my investigative reporting hat, and sent an email to evite support asking what went wrong on NYE.  They replied with an email which clearly was anot written by a human, which lead me to believe that perhaps the outage was caused by a take-over of robots.  Anyway, I did not give up that easily and replied again this time with a concise: “What caused the outage?”  I haven’t heard back yet, but I’ll keep you posted!

Universal Instruments

I’ve written before about how great Netflix streaming movies are.  The library isn’t spectacular; however, if you’re into documentaries, you can instantly watch a huge selection.  I love docs, and over the past couple weeks I’ve seen a few specifically about artists: Rivers and Tides, Scratch, B-Boy Planet, and Touch the Sound.

Scratch is about turntabalism, a musical form where the instruments are record players.  While these turntables produce highly unique sounds, they also are capable of mimicking any other instrument depending on the given input (i.e. record).  This will instantly remind any computer scientist of universal Turing machines, which are capable of mimicking any other Turing machine.  (Turing Machines, first defined by Alan Turing, are the basis of all computation including human intelligence (more about this in future posts)).

A musical instrument which can mimic any other might be called a “universal instrument.”  It seems there are 2 categories of universal machines: audio players which can play an arbitrary input (e.g. record players, cd players, mp3 players), and instruments which can change their tones in real-time (e.g. tone generators, synthesizers, computers).  Any device which can output arbitrary sine waves in unison can re-create any other instrument due to Fourier decomposition.

Some might debate whether a cd player is really an instrument, but it becomes clear when you realize a musician can manipulate the output through even rudimentary controls (e.g. seeking, volume).   A more realistic debate is whether such a player is really a universal instrument, if all of the information is only in the input string.  Interestingly, this parallels a similar debate about a disputed univeral Turing machine! Stephen Wolfram offered $25,000 for a proof that this machine was in fact universal.  It only has 2 states and 3 symbols and is the simplest possible universal machine, although some have debated whether the universality is only a result of a specific input, which actually encodes the universality, and not the machine itself.

Group Theory

I already wrote about Set theory and I eventually want to write about symmetry, so this seems like the perfect opportunity to discuss Group theory.  Let’s start where we left off with Set theory.  We had a very abstract concept of a Set: a collection of “things”.  Then we added some basic structure to that collection (the operation of set concatenation), and before we knew it we were counting and adding.

Well, to formalize it a bit, when you take a set and add a binary operation, and an identity element, then what you get is called a monoid.  Monoids are extremely abstract yet very powerful.  (In a way they even form the underpinning of all of computer science, where the set is a collection of functions, and the product is simply chaining these functions together, called function composition, and the identity is simply a “noop“.)  I’ll talk more about this in a future post because it is so cool how these ideas tie together.

A Group is just like a Monoid, except every element in the set must also contain its inverse.  When an element operates on its inverse, it results in the identity!  Some basic examples, are the integers,  , where every element also has its addtive inverse, called its “negative”.  Another example are the rationals, , where every element has its multiplicative inverse, called its “reciprocal”.  In the former example, the operation is addition and addtive identity is 0, while in the latter the product is multiplication and the multiplicative identity is 1.  Both of these groups also commute (i.e. the order of operation does not matter), and we call these groups “abelian“.  They are named after the mathematician Niels Henrik Abel, but strangely the word is not capitalized.

These groups may seem pretty abstract at first, but here are a few more tangible examples.  First, is that to physicists, a set with elements and their inverses will immediately remind one of a set of particles and their antiparticles.  But we can actually get much more tangible than that if we pull the same trick we pulled above with our monoid:  instead of thinking about objects, get Categorical, and think about processes.  It’s easy to imagine a set of transformations and their inverses: raise and lower, shrink and grow, cut and paste.  All of these examples have the identity of  “do nothing”.

Groups are strongly related to symmetry because an object which is equivalent to the original after transformations is at the heart of symmetry!  In future posts we will talk about the groups of rotations and reflections to explore these concepts.

Biodynamic Marketing

Marketing is not only a good way to sell a product, but, quite remarkably, it is also a way to increase the value a product.  If you read, Malcolm Gladwell’s book, Blink: The Power of Thinking Without Thinking, you might remember the research of Louis Cheskin.  He was one of the first researchers to apply scientific principles to marketing.  In several studies, by modifying only the packaging, the consumers would report different qualities in identical products!

I live in the San Francisco Bay Area, and there is nothing quite like the wine market in this area.  Literally thousands of different wines, which probably only experts could discern between, are fighting for consumers dollars.  One variety of wine which is doing quite well in the Bay Area marketplace, is labeled as “Biodynamic”.  I’ve had biodyanic wine in the past, I just assumed it meant “organic” and/or grown properly with the local ecology (whatever that means).  I was never sure what it meant really, except it was obvious the name was marketing gold.  I didn’t think much about it though, until I read a remarkable article in a local free paper, SF Weekly, about the phenomenom.

It turns out, Biodyanic wine is based on the occult, astrology, and bullshit (yes, both meanings).  There are ritualistic preparations involving burying animal parts stuffed with various substances where they can ferment for a season.  All of this is done in “correspondence” with the stars and planets.

So this leads to an interesting marketing conundrum: The marketing focuses on the term “biodynamic” and other hot marketing buzzwords such as “organic”, “green”, and “eco-friendly”, but it needs to hide or minimize the occult rituals.  We must wait and see how the marketing proceeds, but I know one thing: I will stay away from these wacky wines!

Our Ribosome

When you think about nano-machines, which perform a complex mechanical operations at the molecular level, you might think of science-fiction and the promise of nanotechnology.  Well, one of the most incredible nanomachines is in our cells: the Ribosome!  The magnificent contraption created after hundreds of millions of years of evolution reads an mRNA strand as input, and outputs a protein made of amino acids.  (Yes, we read about these chilralitic wonders in a previous post.)

The ribosome is found in all living cells, both Eukaryotes (protozoa, algae, humans, etc . . .) and Prokaryotes (bacteria and archaea).  It is composed of 2 subunits, one large and one small.  For Prokaryotes the small subunit is labeled 30S, and the large subunit 50S.  For Eukaryotes, they are 40S and 60S respctively.  (The S is for Svedberg units, a measure of sedimentation.)  The are a composed of a complicated intertwining of proteins and rRNA and look like this:

The small subunit on the left contains an RNA molecule (cyan) and 20 proteins (dark blue); the large subunit on the right contains two RNA molecules (grey and slate) and more than 30 proteins (magenta). The image also shows a transfer RNA (orange) bound to the active site of the ribosome. (Harry Noller, UCSC)

Here’s how the process works in Prokaryotes:

1. After mRNA is transctibed from DNA, it reaches (I’m not sure how), the small Ribosome 30S subunit.  Attached to 30S are 2 initiation factors, IF1 and IF3, which keep 30S seperated from the larger 50S.  the mRNA contains a special start codon (usually AUG), which marks the beginning of the mRNA sequence to read for protien synthesis.  A codon is a set of 3 genetic bases, which corresponds to a specific amino acid, but more about that later.
2. IF2 binds to the intitiator tRNA which holds the start anticodon, and IF2 brings this initiator tRNA to the ribosome’s P-site.  If the initiator codon is AUG, the anticodon on the initiator tRNA will be UAC.  Those sequences will bind together.
3. Once IF2 engages, it deposits the initialtor tRNA at the P-site, then all IFs disengage.  This allows 50S to attach with 30S, surround the P-site.
4. The tRNA which contains the anticodon for the next codon triplet in the mRNA sequence is guided into the A-Site inside the ribosome.  Each tRNA contains an anticodon on one end and an amino acid on the other end.  It is these amino acids which will be bound through peptide bond formation to form our protein!
5. After the bond is formed, the tRNA in the P-site is ejected out of the ribosome, and the tRNA in the A-Site is ratcheted into its place.  Then the cycle repeats until the special stop codon on the mRNA is reached.
6. When the stop codon is reached, the subunits disengage, and IF1 and 2 re-engage 30S, starting the process all over gain.

There is a large amount of research into modeling this incredible process.  One example is this remarkable video produced by the Weizmann and Max-Planck Institutes:

UPDATE:  There is some debate as to the realism of this video.  Unfortunately I have not found much information on it, which leads me to believe that this video is only remotely representative of actual processes.   It is still quite instructive, so please just take it with a grain of salt.