300 East 33^rd Street, Suite 4N

1. Abstract

This is the first progress report regarding our new effort to write demonstration programs illustrating principles of Digital Morse Theory. We have written prototype software to build criticality graphs for DNA binding affinity trees at different at all affinity values. We have also written C++ software classes to permit building criticality graphs in 2d gray pixel levels. Though much more work remains, adequate progress has been made in illustrating the disparate application areas of Digital Morse Theory in data exploration.

3. Discussion
1. Visible Human Data radiologic Image contouring and region identification using Digital Morse Theory.

Our work to date has focused on building a strong software foundation for the programming effort that we expect will follow using multiple graduate students and programmers. Our goal in this phase of the effort is to start the software effort off on a robust multi threaded shared memory programming model. This base can support many analysis processes that will join a pool of pixels and decomposition tree data that is always resident in shared memory. Our focus is NOT on the pixels, but rather on the Morse decomposition of the pixels. All subsequent operations will be on the decomposed data, instead of the raw pixels.

Indeed, once we have proven a robust Morse decomposition kernel, we no longer will keep pixels in memory at all. Looking at images derived form the Morse decomposed data will be indistinguishable from raw pixel images except in the way that the images scale at different resolutions.

Our software effort is being supported also in part with software and technical support from Silicon Graphics, Inc. and from the newly founded Scriptics Corporation. We are building our software effort using the TCL scripting language developed by John Ousterhout, Ph.D. for GUI development. We are looking forward to using extensions of the TK GUI library for both data display and control. We also anticipate modifying the GUI’s to include MUI’s (Musical User Interfaces), building on our previous effort in Tactical Audio. There is much in image understanding that can be learned from using musical understanding that has yet to be explored. A Morse Decomposition of an image is directly analogous to a Schenkerian Analysis of a musical composition.

The skeletal framework of our system consists of a group of Tk/Tcl GUI’s that directly manipulate shared memory values. The shared memory segment is allocated using the SGI Arena memory allocation package. This shared memory is memory mapped to a file that is the external handle that all client processes attach to. As this code is being designed to run on a supercomputer in parallel, each process checks for locked code segments and is synchronized by barriers. We have found that the GUI and interaction code makes very heavy use of a single CPU. We are writing this code with the expectation that we will move to a multi-user CPU system as the effort matures. We are also working with Scriptics to improve the Tk display code so that it is not such a CPU hog. We have selected Tk/Tcl because we intend to us it as a research tool, not just a GUI library. We have already made a number of modifications to the Tk/Tcl public source code to manage shared memory access that we hope will become incorporated into the public distributions.

Major modules and classes under development at this time include:

Shared Memory root:

This instances a new shared memory segment and file.

It also remains running as a ‘heartbeat’ process to keep the shared memory segment active and alive in the CPU in the event that there are no other processes keeping the segment alive (a ‘keep alive’ process)

Pixel Loader:

This loads into memory raw pixels. By reading the magic numbers and the file image header, we hope to automatically interpret what kind of image we have loaded in order to display it. In the all too frequent case of loading an unknown image format, we can cohere an image out of the display or the graph by adjusting the pixel properties mask, and the rows and columns. My goal here is to make an ‘Image Analysis break out box’; a tool for peering into unknown image formats that recovers essential image format information such as rows, columns, pixel size, and such. As we develop experience with a variety of different image formats, we can build ‘magic’ tables to distinguish each image format automatically.

Display Window:

We will use one window for both 2d-slice display and 3d-isosurface display. We will be able to pull back in three dimensions and continuously transition from a pixel display to a isosurface display in 2 and three dimensions. Our goal there is to show that there is a continuous relationship between the 2d Digital Morse Theory decomposition and the 3d Digital Morse Theory decomposition.

 

Graph Window:

This window displays the DMT criticality graph of the ROI shown in the Display Window. This window will have the practical application of being able to select objects in the 2 or three dimensional scene without problems in bigger objects obscuring enclosed objects and object crowding. Indeed, these are major problems in any 3d display picking system. Frequently, the details you want to zoom in on are only 1 or 2 pixels big on the display. A side benefit is that we can do picking and selecting on 4, and more dimensional data without having multiple orthogonal display windows.

 

 

Overall design is to focus on decomposition of different and varied datasets into one, registered, DMT decomposition and a graph (tree) representation for further exploration by haptic, graphics, and sound exploration.

 

2. The Hierarchicalization of DNA-Binding Drug Affinity Data using an Application of Digital Morse Theory.

We developed an implementation of Digital Morse Theory as a means to visualize DNA-binding drug affinities over the set of 256 4-base pair oligonucleotides (e.g. AAAA-TTTT). This exercise was intended to demonstrate the wide-applicability of Digital Morse Theory-related concepts to the hierarchical ordering of information.

Our technique is derived from the insight that it is possible to construct a tree representation given an arbitrary set of 4-base pair oligonucleotides (e.g. AAAA, CCAA, CGTT, TAAA), for example:

• Figure 1: An affinity tree consisting of four 4-base pair oligonucleotides.

Accordingly, it is possible to construct an array of affinity trees by varying a threshold through a data-set of affinity rankings for the entire set of 256 4-base pair oligonucleotides. The resulting array of trees, or meta-tree, would be constructed by appending only those trees for a particular threshold level where the total accumulated number of terminals changes.

We implemented this technique as a set of C++ classes. The code implementing these classes and descriptions of their functions follows below. In our class-naming system, we prefix the name of each class by the letters "AT", standing for "Affinity Tree".

1. An Example Program Using the ATMetatree Class

The following code illustrates a simple utilization of the ATMetatree class. The function of this utilization may be summarized as follows:

• Define settings for the experiment.
• Construct an ATMetatree object using the experiment settings.
• Output the experiment results by stepping through the resulting meta-tree.

1. Implementation of the ATMetatree Class

The ATMetatree class provides an interface to the lower-level classes, as well as an array to contain the set of subsidiary affinity trees. The function of this class may be summarized as follows:

• Load the data.
• Increment through the data using a low-pass filter.
• Allocate and propagate a new tree object where the accumulated number of terminals found changes.

1. Implementation of the ATData Class

The ATData class provides the basic functionality to load and parse a data-set. The data file format consists of a table of 256 floating point values that represent the percent rank for the oligonucleotide corresponding to that index.

//////////////////////////////////////////////////////////////////////

//

// ATData.cpp: Data handler for ATParser %R affinity data.

//

//////////////////////////////////////////////////////////////////////

//

#if !defined(AFX_ATDATA_CPP__CC7B9F23_DE01_11D1_BF09_006097958E47__INCLUDED_)

#define AFX_ATDATA_CPP__CC7B9F23_DE01_11D1_BF09_006097958E47__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif

//////////////////////////////////////////////////////////////////////

//

//////////////////////////////////////////////////////////////////////

#include <io.h>

#include <stdio.h>

//////////////////////////////////////////////////////////////////////

//

//////////////////////////////////////////////////////////////////////

#define __noligos__ 256

#define __linebuf__ 80

//////////////////////////////////////////////////////////////////////

// atdata

//////////////////////////////////////////////////////////////////////

class atdata

{

public:

bool m_err; //file read error flag

double m_inbuf[__noligos__]; //the raw data buffer

double m_data[__noligos__]; //the filtered data buffer

public:

atdata(char*);

virtual ~atdata();

};

//////////////////////////////////////////////////////////////////////

// atdata::atdata

//////////////////////////////////////////////////////////////////////

atdata::atdata(char *datafile){

FILE *stream; //pointer to the file stream

char lbuffer[__linebuf__]; //line buffer

if(!(_access(datafile,0))&&!(_access(datafile,4))){ //init if file exists

for(int i=0;i<__linebuf__;i++) lbuffer[i]=NULL; //init line buffer

for(i=0;i<__noligos__;i++) m_inbuf[i]=m_data[i]=0; //init buffers

if((stream=fopen(datafile,"r"))!=NULL){ //open the file stream for reading

m_err=false;

for(i=0;i<__noligos__,!feof(stream);i++){ //read 256 if not end of file

if((fgets(lbuffer,__linebuf__,stream))!=NULL) //read a line

sscanf(lbuffer,"%lf",&m_inbuf[i]); //append to the raw data buffer

if(ferror(stream)){

m_err=true; //set error on the file stream

break;

}

for(int j=0;j<__linebuf__;j++) lbuffer[j]=NULL; //reset the line buffer

}

} else m_err=true;

fclose(stream); //close the file stream

} else m_err=true;

}

//////////////////////////////////////////////////////////////////////

// atdata::~atdata

//////////////////////////////////////////////////////////////////////

atdata::~atdata(){

}

//////////////////////////////////////////////////////////////////////

#undef __noligos__

#undef __linebuf__

#endif // !defined(AFX_ATDATA_CPP__CC7B9F23_DE01_11D1_BF09_006097958E47__INCLUDED_)

//////////////////////////////////////////////////////////////////////

 

 

2. Implementation of the ATTree Class

The ATTtree class forms a tree representation for a given set of oligonucleotides. For convenience, the tree representation is embedded within a hypercube.

//////////////////////////////////////////////////////////////////////

//

// attree.cpp: implementation of the attree class.

//

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ATTREE_CPP__CC7B9F23_DE01_11D1_BF09_006097958E49__INCLUDED_)

#define AFX_ATTREE_CPP__CC7B9F23_DE01_11D1_BF09_006097958E49__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif

//////////////////////////////////////////////////////////////////////

//

//////////////////////////////////////////////////////////////////////

#include "ATCode.cpp"

#include "ATData.cpp"

//////////////////////////////////////////////////////////////////////

//

//////////////////////////////////////////////////////////////////////

#define __base__ 4

#define __noligos__ 256

//////////////////////////////////////////////////////////////////////

// attree declaration

//////////////////////////////////////////////////////////////////////

class attree

{

public:

double m_threshold; //the threshold at which the tree is in evidence

double m_hypercube

[__base__]

[__base__]

[__base__]

[__base__]; //hypercube containing the tree

int m_terminals; //number of terminals in the hypercube

public:

attree(atdata*);

virtual ~attree();

};

//////////////////////////////////////////////////////////////////////

// attree implementation

//////////////////////////////////////////////////////////////////////

attree::attree(atdata *data){

atcode code; //create a new code object

m_terminals=0; //there are no terminals as yet

for(int i=0;i<__base__;i++){ //init the hypercube

for(int j=0;j<__base__;j++){

for(int k=0;k<__base__;k++){

for(int l=0;l<__base__;l++){

m_hypercube[i][j][k][l]=NULL;

}

}

}

}

for(i=0;i<__noligos__;i++){

if(data->m_data[i]>-1){ //insert oligonucleotide if data not null

code.code(i);

m_hypercube

[code.m_num[0]]

[code.m_num[1]]

[code.m_num[2]]

[code.m_num[3]]=data->m_data[i]; //add terminal

m_terminals++;

}

}

}

//////////////////////////////////////////////////////////////////////

// attree::~attree

//////////////////////////////////////////////////////////////////////

attree::~attree(){

}

//////////////////////////////////////////////////////////////////////

#undef __base__

#undef __noligos__

#endif // !defined(AFX_ATTREE_CPP__CC7B9F23_DE01_11D1_BF09_006097958E49__INCLUDED_)

//////////////////////////////////////////////////////////////////////

 

 

3. Implementation of the ATCode Class

The ATCode class provides basic functionality for generating and manipulating 4-base pair oligonucleotides, or 4-digit quaternary words, given a decimal representation from (e.g. 0-255).