frameworker

August 1, 2008

Gel Tracker

Filed under: Uncategorized — frameworker @ 3:23 am

Gel Tracker was a program used to “track and extract” DNA data from “sequenced gels.” It was my full-time project from December 1996 until June 1998. I wrote it in C++ using MacApp.

Gel Tracker drew lines, interactively, down the center of each lane on a gel to identify the data slices to be extracted for sequencing. It also used an auto-tracking algorithm, I wrote, that radically improved tracking accuracy and efficiency. I also implemented a panel display to visualize chromatograms for tracking validation.

Milestones Leading to Automated DNA Sequencing

This is not a comprehensive history of the “Genomic universe,” just a rough timeline to show where Gel Tracking fit into the scheme of things in DNA sequencing.

1953 – The molecular structure of the DNA molecule is discovered. (Watson & Crick)
1977 – DNA sequencing by electrophoresis (Frederick Sanger)
1983 – PCR enables rapid amplification of DNA (Kary Mullis)
1984 – Four color dye method of sequencing developed (Tim Hunkapillar)

Automated DNA Sequencers

1986 – ABI 370A
1990 – ABI 373A
1995 – ABI 377
1996 – ABI 377 96-lanes

Tracking a Gel

The early sequencers used slab gels. The “sequenced gel” looked like a series of multi-colored ribbons running down a glass plate plate. It was necessary to “track the gel,” that is, to define the locus of each lane, so the underlying data could be extracted, the next step in the bioinformatic data stream.

When you look at a Gel Image, you see a four color image: Red, Green, Yellow and Blue. While each point in a gel image has four intensity values, one for each dye, only the most intense color is displayed at each pixel to enhance the visualization of DNA sequence data.

Gel Tracker window containing a tracked 96-lane gel:

FAB2B15E-DFCB-419D-9E6E-F1265D3B2C1B.jpg

You can see comb makers to the left and lane markers above the gel. The lanes are depicted as vertical white lines with selection handles at points where the lanes and combs intersect. (The handles turn red if they are “selected.”)

The Interface

As “Moore’s Law” played out in sequencing, lane geometry became increasingly tight. With the advent of the 96 lane sequencer, lane separation was no longer always obvious. So it became necessary to augment user tracking with algorithms to largely automate the tracking process.

The 96-lane gel has a gap between two sets of 48 lanes. If a gel was good*, and a lot of them were, you could track the outside lanes of each 48 lane group. Then interpolate each of the two interior lane sets and auto-track them. Sometimes, auto-tracking a second time would improve the results slightly, where the auto tracking algorithm had been a bit “conservative” for the given data.

Selection was just a matter of dragging a selection rectangle over the lane markers you wanted to include. You could, additionally, Command-click to invert the selection state of individual lanes or Shift-click to affect multiple lanes.

* High flourescence saturation, reactions completed for practically all lanes (i.e. no “dropouts”), uniform lane spacing.

Visualizing DNA Data for Extraction

The key to optimizing gel tracking was to auto-track good gels but to have an interface that visualized the gel for manual tracking as a fall-back for bad gels. Adding the chromatogram panel accomplished that by allowing users to interactively observe a slice of the gel as it was being tracked. By noticing the amplitude of the chromatogram and watching its “Chrom value,” the user could find the optimal path for any lane.

The chromatogram panel allows you to visualize a slice of the gel when a single lane is selected. It’s implemented with a synchronous scroller so that it always matches the selected lane as the gel is zoomed and scrolled.

In 1987, as a Christmas present to his wife who was a geologist, Larry Tesler who had invented MacApp, added Synchronous Scrolling to MacApp for visualizing scientific information. Here, ten years later, I was also using it for just that, in biochemestry.

Visualizing chromatogram data conferred many benefits:

• Made it easier to Track difficult parts of a gel.
• Provided interactive feedback to shorten the “learning-curve” for new users.
• Helped users develop confidence in auto-tracking and understand other Gel Tracker features.
• Was essential for testing Gel Tracker, especially in conjunction with the “Chrom value” field.

Tracking detail with chromatogram:

DE58E157-0A5F-4D24-952C-A20AAECF63EF.jpg

Gel Tracker Architecture

Gel Tracker was implented with MacApp which provided general mechanisms for user interaction: selection, dragging, tracking feedback and one level of undo/redo. I loved MacApp!

MacApp’s View architecture perfectly supported Gel Tracking and the addition of USynchScroller, used to visualize “data slices,” was “icing on the cake”!

The adjustable lane map overlaid the gel view. When the lanes were retracked either manually or automatically, the affected extent of the gel view was invalidated and redrawn, using an offscreen bitmap, prior to updating the lane map.

Scrolling and Zooming

Scrolling and zooming performance was quite good, minimizing flicker, because of the offscreen bitmap. But to further reduce flicker, I kept a grey scroller underneath the gel. Only visible during invalidation, it made the perceived flicker practically vanish!

In the figure, “Tracking detail with chromatogram,” you can see the zoom controls between the ACGT buttons and the Sample Name text field. The gel is shown fully zoomed-in, so the horizontal and vertical magnification controls are dimmed.

When zooming, lane map positioning is conserved by numerically scaling the lane map. It’s also necessary to compensate for the fact that the zoomed image representation may be “downsampled,” a slight wrinkle.

Downsampling is a technique to visualize a reduced gel image. Rather than taking every nth vertical pixel, swaths of contiguous pixels are taken – still in proportion to the zoom factor – to maintain the characteristic appearance of DNA data.

Auto-tracking

Auto-tracking was performed, first, by shifting each tracking segment left or right, then by adjusting its slope and, finally, by “annealing” the endpoints of adjoining segments to maximize the lane’s image value.

The lane’s image value is the sum of intensity values for each pixel under each of its segments.

“YOU CAN ONLY TELL THE SHAPES OF THINGS BY LOOKING AT THEIR EDGES…”

Of importance, the first two stages of auto-tracking are constrained by “edge detection” when the number of color changes between an original and alternate segment position exceeds a preset value.

When this occurs, it is assumed that a lane boundary has been reached and auto-tracking is halted for that stage.

In honor of Tim Hunkapillar, who besides being a world-class biochemist, was a big fan of The Rocky Horror Picture Show, the first phase of auto-tracking was eponymously named “The Time-Warp,” for the song from that movie containing the lyric: “just a jump to the left, then a jump to the right.”

An Anecdote

Early in the project, I encountered a really weird toolbox “bug” that drove me nuts. In my “jihad” to defeat it, I was fortunate to find one of the last existing copies of Programming QuickDraw (which had been published six years earlier, in 1991) in Stacey’s Bookstore in Palo Alto. When I still couldn’t figure out how to solve the problem, I called the author, David Surovell, who graciously spoke with me about it! In the end, the solution involved “QuickDraw Voodoo.” But David’s assistance in ruling everything else out, helped me keep my sanity and find the eventual solution!

Advertisements

TreeBuilder

Filed under: Uncategorized — frameworker @ 3:19 am

FF37591F-F729-46D0-A25B-D8DE27DCCB77.jpg

Programs are made by fools like me,
But only God can build a tree.

(with apologies to Joyce Kilmer)

Overview

TreeBuilder is a Macintosh Classic program that makes it easy to draw tree graphs with text boxes as the nodes. The trees may be used as organization charts or for visual maps to navigate text-based material, hypermedia or multimedia.

63FC8622-8E49-4FCE-A33E-30BB01A3F909.jpg

Creating a tree is an intuitive process, giving you the shortest, simplest path to visualizing hierarchic models. You lay out trees by manipulating them directly: sketching trees; selecting, resizing and dragging nodes. To build a tree you create a new document containing a root node and sketch or paste branches and subtrees. Hierarchic orientation is top-down with children beneath their parents. You can type or paste text into the tree’s nodes, then style that text using any font available on your system. You can automatically clean up tree layout at any time.

A number of specific operations exploit the property of hierarchy. Subtrees may be selected, dragged, cut, copied, cleared or pasted within TreeBuilder documents. Subtrees may be collapsed and expanded.

TreeBuilder fully supports the Clipboard and supports one level of Undo for all pertinent commands. Written with MacApp, TreeBuilder strives for ease of use and for robust and reliable operation on the Macintosh.

Fly-Through

Constructing a tree graph with TreeBuilder is quick and easy. Build the tree described in this fly-through, and you will understand the basics.

Double-click on the TreeBuilder icon to start the program. An untitled document will appear in a new window. The new document contains one box. This will be the “root” node of your tree. The node is selected already, as you can see from the black squares at its corners. Those squares are “handles” you can use to change the size of the box. If you have unselected the box—for example, by clicking somewhere else in the window—select it again by moving the mouse cursor over it and clicking once.

D3FC7284-7B35-4D81-B4A8-30076A513DC3.jpg

Now set the type format for the tree. Defaults are already set, but let’s change them. Click the Font menu and choose “Times”. Click the Size menu and choose “10”. Click the Justification menu and choose “Center justified”. These selections will become the new default for your document, but you can change all or part of the text in any node by highlighting it and making new choices in the Font, Size, Style and Justification menus.

Move the mouse cursor over the box and you will see it turn into an I-beam text cursor.

F3A8152D-AD27-4290-BEC5-C2940BBF96E8.jpg

Click anywhere inside the box, and a blinking vertical bar—the text-insertion point—will appear.

85F808D3-FA9F-491B-96E0-5996FDFA2F07.jpg

Type in “The Big Cheese.” You’ll notice that there is not room for all the text. To make enough room, click a corner of the box and drag it to make the box larger. Even though the selection handles aren’t visible when you’re in text editing mode, you can resize the node you are working in, just as you can when the handles are visible.

649F1B82-1674-4EB0-96C9-31AD24F3A9F5.jpg

Hit the Return key to start a new line. (Text does not wrap to the next line when it reaches the edge of the text area inside a node.) Type in “A world of healthy food.”

8C0A11B3-8922-4CDB-81AD-773F17A711CB.jpg

Now let’s emphasize the first line—the one that says “The Big Cheese.” Move the I-beam cursor just to the left of the T, click and hold the mouse button, then drag the cursor until all of the first line is highlighted. Click the Size menu and choose 12. Click the Style menu and choose Bold.

861096C6-D615-4728-B6EE-DBB6C8B391A2.jpg

Now let’s put some branches on the tree. At the bottom of the node, you’ll see a small diamond called the clone control. Click the clone control with the mouse pointer and it turns black to show it is active. Move the cursor down below the top node and it turns into a “+” sign. This lets you know you are in an area where you can draw a new node. Click and hold the mouse button as you drag the cursor to create the box for a new node. Don’t worry too much about the exact size and position of the node. In a few minutes we’ll use an automatic feature of TreeBuilder to clean up the layout.

CBDE424F-7B60-4672-87A0-B30A663ED97D.jpg

There is a text insertion point blinking inside the new node you’ve just created. Type in “Snack Items.”

Now click the clone control at the bottom of the Snack Items node. Repeat the process you used a minute ago and draw a new node below and to the left of the Snack Items node. Type “Cheese Crackers” into that new node. Now move the cursor just to the right of the Cheese Crackers node. You’ll see the “+” cursor, and the clone control on the Snack Items node is still black. This shows you that you can create another node, and it will be a “child” of the Snack Items node.

DF3E20B1-129F-4C08-AFBD-78F91BF3D902.jpg

So make a node to the right of the Cheese Crackers box and type in “Cheese Spread.”

To save a bit of work, we want to select the whole Snack Items subtree and copy it. Double-click on the Snack Items box and you’ll see selection handles at the corners of all the boxes in that tree, indicating that all three nodes are selected.

F6672035-CF73-4316-93BB-0AA96091EF47.jpg

Click the Edit menu and choose Copy. This stores the subtree on the clipboard. If you want to be sure it’s there, look at the clipboard by clicking the Edit menu and choosing Show Clipboard. Make a second branch under The Big Cheese. Click the clone control on the The Big Cheese node. Click and drag to create a new node to the right of the Snack Items node. You don’t want to type any text here yet, so click on the work area outside the node to deselect it. Now click once on the new node; the handles will appear to indicate the node is selected. From the Edit menu, choose Paste and a copy of the Snack Items subtree will appear, replacing the node you just created. The pasted tree will be selected.

1341E791-5E19-476B-B282-79C5277A4269.jpg

If the new subtree is overlapping the old one, you can move the whole subtree by clicking inside any box on the subtree and holding the mouse button down while you drag the subtree to a new position.

Hold down the Shift key and double-click the copy of the Snack Items node to deselect the whole subtree. Now move the cursor over the copied Snack Items box, click and drag over the text to highlight it, and type in “The Real Thing.” Use the same procedure to change the copied Cheese Crackers to “The Whole Wheel” and Cheese Spread to “Quick Chunks.” Click anywhere in the work area to deselect all the nodes.

Our fly-through graph is just about finished. We just want to clean it up and dress it up a bit. Click the Layout menu and choose Clean Up Tree. TreeBuilder will make all the boxes the same size—big enough to hold the largest block of text—and line them up neatly on the page. Now from the Layout menu choose Hide Tree State, then go back to the Layout menu and choose Shadowed Borders.

81C03D0A-E5D9-4346-8D07-C991F7645445.jpg

From the File menu, choose Save and save the graph as Big Cheese. To print out a copy, go to the File menu and choose print. If you want to include your graph in a document created in a different program, double-click on the The Big Cheese node to select the entire tree, then go to the Edit menu and choose Copy. This puts the graph on the Clipboard. Switch to the document where you want to use the graph, choose Paste from the Edit menu of the second program, and the graph will be pasted in as a PICT graphic.

You can download TreeBuilder and its User’s Guide here.

Create a free website or blog at WordPress.com.