ADN_Viewer: A Software Framework For 3D Modeling and Stereoscopic Visualization of the Genome

Rachid Gherbi
LIMSI-CNRS, Université Paris-Sud
BP 133, 91403 Orsay cedex
Tel.: +33 1 69 85 81 64
Fax.: +33 1 69 85 80 88
 Email: gherbi@limsi.fr

Joan Hérisson
LIMSI-CNRS, Université Paris-Sud
BP 133, 91403 Orsay cedex
web: http://www.limsi.fr
 Email: herisson@limsi.fr

Contents 

Abstract
Biologists currently study genomic sequences using a textual form of representation that does not provide them with a global view of the sequences. This paper presents a new tool- the ADN-Viewer - for the three dimensional modeling and stereoscopic visualization of the genome. Biologists can use this tool for such things as rotation and translation of molecules, zooms, data extractions, etc. We've had to develop solutions for managing complex graphical displays (genetic information concerns tens to several hundred million atoms) and user interaction with objects in a virtual environment requiring multiple representations in order to carry out a variety of biologic analysis. While basically designed for in silico analysis of the DNA 3d structure, the ADN_Viewer can also provide biologists with 3D databases. Work presented here is the first stage of an on-going program aimed at managing information rich 3D environments and interaction with virtual objects located in these environments. This program should make it possible in the long run to directly produce genomic multimedia documents for teaching purposes.

Keywords:StereoscopicVisualization,Navigation, 3d Representation, Human-Computer Interaction, Scientific Data, Genome, DNA

1. Introduction
This paper describes the functionalities of a software tool named ADN_Viewer currently being designed and implemented by the Gesture and Image (GI) team of the Human-Computer Communication Department at LIMSI-CNRS in France (Laboratoire d?Informatique pour la Mécanique et les Sciences de l?Ingénieur du Centre National de la Recherche Scientifique) This bioinformatics software enables 3D modeling and stereoscopic visualization of genomic sequences and was developed using standard programming tools such as C, C++, Tcl-Tk and uses the graphic library OpenGL [9]. 
Collaboration has recently begun between computer scientists at LIMSI and biologists at the Genetic and Microbiology Institute of Orsay (IGM) in order to study and analyze the three-dimensional structures of the genome [2][6][7]. This type of study augments the textual study of genomic sequences with visual and global representations of living organisms which allows the user to graphically rotate and translate molecules, zoom in on particular features and extract out data of specific interest from the wealth of information available.
This multi-disciplinary work is at the interface of two innovative fields: genomics (Biology) and virtual reality for scientific visualization [13][14] (Computer Science). Three objectives are being pursued:
To prove the usefulness of the ADN_Viewer for the in silico analysis of DNA three-dimensional structures;
To address the general problem of designing and implementing virtual reality applications, namely that of managing extremely rich information environments ("scenes") as well as the human interactions with the virtual objects located in those environments;
And finally, to produce multimedia documents for teaching purposes. 

2. General presentation of ADN_Viewer

2.1 Some Genomic Definitions [11][12]

The nucleic acids are the fundamental components of the live cell and carry its genetic information. They are polymers made up of nucleotides and, according to the type of ooze (sugar) making up these nucleotides, they can be classed in two groups: 
deoxyribonucleic acid (DNA), localized essentially inthe cellular core,
and the ribonucleic acids (RNA) which are more abundant in the cytoplasm. 
The DNA is a double strand formed by 4 nucleotides A, C, G, and T. The succession of thousands, even millions of nucleotides constitute the DNA molecule. The two strands are anti-parallel and complementary: for example, each nucleotide A of a strand corresponds to the nucleotide T of another strand (and vice versa) and, in the same way, each nucleotide C of a strand corresponds to the nucleotide G of another strand (and vice versa). 

Figure 1: The DNA is a double strand

We refer to reading a nucleotide when one strand of the DNA is read; but our application also requires reading the two strands bound together and we will then speak about how to read a "plate".

2.2 The Functional Architecture of the ADN_Viewer

Figure 2: Functional architecture of ADN_Viewer

2.3 Input Data 2.3.1 The DNA Sequence

A file sequence contains the nucleotide chain in the form of letters (ACGT) as well as other information such as the name of the organism, the numerical indexing of the sequence, or gene names. The structure of this file depends upon the format used which is generally either :
·The FASTA format, used by GenBank,
http://www2.ncbi.nlm.nih.gov/genbank/query_form.html),
·Or the GCG format, used by the university of Stanford,
http://www.stanford.edu).
The size of the sequences varies, but we can divide the whole of the known sequences into 3 categories:

The nucleic sequence is small and doesn't generally exceed about fifteen nucleotides which often represent the vicinity close to a start codon (or a stop codon) of a gene,

·Genic sequences are middle sized, containing several hundred to a few thousand nucleotides, which are generally genes,
·and finally a genomic sequence are often very big (³ 10 000), corresponding to the description of complete molecules (large sequences are composed of several billions of nucleotides).

2.3.2  3D rule-based construction of DNA

The rules of 3D construction [5] provide geometrical information on the DNA molecule. These rules are generic with any sequence, and any modification of one of these rules amounts to changing the geometrical model of the molecule. Indeed, they are composed of a table of rotations and a translation. The table of rotations contains 3 values of angles (one by axis) for each succession of two nucleotides; these values represent relative rotations between the current plate and the previous plate. The translation represents the vertical distance between two successive plates. 

 

Figure 3: Sequence + rules = 3D visualization

2.4 Input Data

When a letter representing a nucleotide is read, construction rules are applied which correspond to the couple (previous letter, current letter) and systematically reiterated on the whole sequence in order to calculate the absolute 3D coordinates of each nucleotide. We obtain the three-dimensional structure of the DNA molecule shown in Figure 3

3.Representation, Visualization and Interaction

3.1 Modeling and Representation

3.1.1 Genomic Representation

In order to visualize objects in a 3D environment, representations have to be adjusted in order to account for the object's size. A very large molecule will be shown with less detail than smaller ones. For example, Figure 4 only shows the two Watson and Crick strands of the very large genomic sequences defined above.


Figure4: Genomic representation of a sequence including 80.000 nucleotides.

3.1.2 Genic representation

On parts of molecules such as genes, it is useful to have information comparing the position of nucleotides with respect to one another. A sphere can be used to model each nucleotide, and each type of nucleotide (A, C, G or T) has a different color. This representation applies to middle sized sequences (cf. Figure 5)
Figure 5: Genic representation of a sequence including 500 nucleotides

3.1.3 Nucleic representation

To observe the vicinity close to a key part of the sequence such as a start codon (3 successive nucleotides), we need to display all the available information on both the atomic structure and the links of each individual nucleotide. Once again a sphere can be used to model each atom composing a nucleotide, and each atom has a single color. This level of representation is biologically and visually relevant only if sequences do not exceed about fifteen nucleotides (cf. Figure 6)

 

Figure6: Nucleic representation of a sequence including 11 bases

3.2 Visualization

To study the molecule of D.N.A., the user can use different modes of visualization: the multi-view and the full-screen modes. 

3.2.1 The Multi-View Mode

The screen is divided into four parts (cf. Figure7) with the display in the top left hand corner providing the user with a general perspective of the scene he or she is observing. This is the main view and serves human-machine interactions for navigation and stereoscopic visualization. The other three views provide the user with full information on the spatiality of the molecule: 
·The top-right corner of the screen displays the molecule from underneath; 
·The bottom-left corner shows the Watson strand of a DNA molecule;
·The bottom-right corner shows the Crick strand 
The goal of the multi-view mode is to reduce as much as possible the cognitive load put on biologists when accessing DNA information through the ADN_Viewer. They immediately see how to work with the system; they don't have to learn what the system can offer them by working through a menu for example. The "hands-on" interface design is directly accessible using a mouse. 

Figure 7: Visualization according to 4 views

3.2.2 The Full-Screen Mode

The full-screen mode offers more comfort of visualization than the multi-view technique and serves other purposes. Two types of full-screens are available with ADN_Viewer :
· a full-screen with a menu (cf.Figure8)
· and a full-screen without a menu (cf.Figure9)
The first gives fast access to the databases (sequences and tables of rotations) and the commands needed to organize data extraction, reset parameters and modify the values of angles and distances, etc.
The second uses the keyboard and the mouse for manipulating the graphical objets visualized on the screen. This specific mode of interaction requires coordinating the use of access devices (mouse and keyboard) and the way in which the graphical display will be modified through their use. This is a particularly difficult question in the context of immersion-based virtual reality plate-forms.

Figure 8: Full-screen with menu

Figure 9: Full-screen without menu

3.3 Stereoscopic visualization

The user has the possibility of visualizing the DNA molecule in relief; the spatiality of the molecule is perceived much better. 

3.3.1 Description of the process
Human being perceives the world of objects which surround them in relief because they see things from the two different points of view of their two eyes. To supply the impression of relief with computers, there are two main technical solutions:
·active stereoscopy,
·or passive stereoscopy.
These two solutions differ both by the hardware used and by the results obtained. However, they use the same approach.
Active stereoscopy requires a particular material device. The computer must be equipped with a suitable card and the user must carry glasses that are synchronized with the screen. Then, from the display point of view, it is necessary to calculate the object from two view points (eyes) and to display the two images one after the other at 60Hz frequency. The glasses synchronized with the displaying frequency of the screen make it possible for each eye to have its own point of view (something which is unfeasible if the two images are displayed simultaneously on the 2d screen). This frequency is too high for the brain to perceive the phenomenon and, consequently, the object appears in relief. 
Passive stereoscopy or anaglyph requires only one pair of colored glasses. The colors (one for each glass) are two complementary colors (in general, red and cyan). As was the case for active stereoscopy, the object is calculate from two different points of view, but instead of displaying the two images one after the other, only one image is shown using different colors to combine the two points of view. These colors are those of the glasses and are in conformity with the projective geometry of the stereoscopy. In fact, colored glasses play the role of chromatic filters and thus offer to each eye its own point of view.
Some stereoscopic visualizations using anaglyph images are give in the following (please use an anaglyph stereoscopic glasses with red and blue colors):

 

3.4 User Interaction with DNA Structures

3.4.1 The mouse

The mouse manages the rotational movements around the molecule. These 2d movements are interpreted as being three-dimensional ones around a sphere (cf. Figure10). 

Figure 10:  Rotations are carried out according to a sphere model.

 

The mouse also gives access to the contextual menu that manages the levels of details and the output of the application. 

3.4.2 The keyboard

The keyboard manages all the functionalities that can be controlled by the mouse, the vertical and horizontal adjustments, as well as the zoom in and out. It also provides the majority of the functionalities that offers the menu.

3.4.3 Extraction

A biologists will generally onlystudy a part of a molecule (for example a gene or a start codon) which can be isolated using theextraction function. This option is used both to select an element for study and to readjust the screen display in order to eliminate unwanted background information. The zoom allows us to givemuch more detail on the small part of the sequence studied. l.

3.4.4 Reference Axis

As shows the Figure 11, the reference axis is a line segment with length equal to the vertical height of the sequence and which passes by the center of first nucleotide of the sequence.

Figure 11: Reference axis

This line is inserted in the three-dimensional representation of the sequence, which provides additional information on spatiality: orientation and distribution of the molecule in space.

3.4.5  Documents produced by ADN_Viewer

DNAtoStillImage is a function that produces a still image (JPEG format) of all information displayed on the screen. These snapshots can be useful during the visualization of a molecule allowing the spatial comparison of several sequences. It is also essential to be able to compare the virtual molecule with the real molecule in order to validate results obtained using the ADN_Viewer. The majority of the images in this paper were obtained using this function.
DNAtoVideo is also implemented, knowing the precise scenario of the video (digital film) which one wants to carry out, and writing some lines of code. This film can be documentary and/or multimedia (presentation document of the software with mixing voice or music). 

4. Genome-data processing

4.1.1 The table of rotations

Each line read in the table of rotations including the 3 values of angles is transformed into a geometrical matrix of transformation that also includes the vertical adjustment between two successive plates. Then 16 matrices corresponding to the 16 combinations of couples within the alphabet {A; C; G; T} are stored in a two-dimensional table. When a letter of the previous nucleotide and the current one are known, a relation can be established between the letters and the indices of the table in order to directly access the corresponding transformation matrix (cf. Figure12). This process of pre-computing appreciably decreases the time needed to calculate the points constituting the sequence. Indeed, to apply a rotation or a translation to an object means calculating the product of matrices. Here, a matrix contains 3 rotations and 1 translation, i.e. we gain a factor 4 each time a sequence is computed.

4.1.2 The Sequences

The letters of a sequence file representing nucleotides are stored in a mono-dimensional table and, then, by applying the matrices of transformations computed above, we calculate the absolute 3D coordinates of each nucleotide, which are stored as well in a mono-dimensional table (cf. Figure12). 

Figure 12: Principe of coordinates computing

Once again this phase of pre-computing saves invaluable time, because, with each movement of the scene, the latter must be entirely recomputed. In the present case, it is enough to traverse the table in which are stored the coordinates of the points and to display the graphic objects according to the level of desired detail (genomic or genic). Once these coordinates are computed, we deduce the coordinates from nucleotides forming the other strand.

For the nucleic representation, the transformation matrices are propagated to each scene display in the following way: first, we compute the coordinates of the two points modeling each nucleotide on the nucleotide plate; second, three rotations and the translation of each plate are obtained by consulting the transformation matrices, but, for a given plate, the third rotation (that around axis Ox) is not represented; finally, the translation between the genomic and the genic levels of representation is obtained by using the points on the spheres modeling the nucleotides but not the rotation around their axis Ox. Indeed, a dumbbell (genic representation) that rotates around axis Ox remains identical to itself (cf. Figure 13).

Figure 13: Alter turning around Ox axis

On the other hand, in the nucleic representation where the layout of the spheres modeling the atoms creates a parallelepiped structure, rotation around Ox axis causes slopes of the plate that must absolutely be represented (cf. Figure 14).

Figure 14: Parallelepiped turning around Ox axis

4.2 Visualization of a Sequence

We saw above that a table is generated to display a DNA sequence. This table is dynamically processed by sampling it to render the complexity of the scenes which have to be visualized. For example, if the represented molecule is big and at a distance, we will not display all its points but perhaps only one out of twenty in order to manage the granularity of the scene. This process applies to all levels of detail; representations of each sphere take into account the distance to the object on the screen.

4.3 The Bounding Box

Our technique for visualization is a box which fixes the limits of the scene visualized - a "bounding box"- and which is dynamically calculated and adjusted for each sequence that has to be shown.. The box is designed to represent all possible spatial orientations of a molecule, providing a cone of visualization which can be parametrized.. When a zoom is carried out, the box moves with the sequence.

5. Video animation

The video  presented here below shows  an anaglyph-based stereoscopic animation .

6. Some present enhancement and future work

6.1   3D Object Clipping

For the moment, we do not engage in 3D object clipping because clipping greatly increases computation time and thus causes a corresponding loss in real time interactivity. Clipping would probably be appropriate to help manage the granularity of scenes, for example, in order to display more details during zooms.

Two approaches exist:

·downstream clipping,

·and upstream clipping.

Downstream clipping is carried out after the matrix has been produced, i.e. when objects are calculated but not yet displayed. The method is not selective and because all the objects are calculated there is no saving in calculation time.

Upstream clipping, on the other hand, is carried out before the matrix is produced and concerns only the objects which will be shown on the screen.A real economy of calculation time can thus be obtained. 

This last approach to clipping interests us since it will enable us to solve the problem stated above.

6.2 Visualization close to en offset part

When a rotation is carried out, the scene turns around a pre-computed fixed point that is the center of the bounding box (we can assimilate this point to the center of gravity of the molecule). On a sequence of small size or an overall visualization of an unspecified molecule, no problem of ergonomics arises. But, when, on a sequence of huge size, we visualize part of the molecule which is far away from the center of rotation, the movements undergo an arm of lever such as it becomes very difficult to control the least small movement.

6.3 Simultaneous Visualization of Several Sequences

Biologists like to work simultaneously with several sequences which requires placing these sequences in the same frame of reference (but in distinct windows) and synchronizing the movements displayed on the screen (i.e. showing the different sequences moving in the same way at the same time).

6.4 Curve computation and analysis

Biologists who analyze the geometrical structures of DNA often work rather on the corresponding cards of a fold. These cards have two dimensions provide partial information on the 3D fold of DNA. This is why it is necessary to integrate a fold map generator [4] within ADN_Viewer. These data will be used as if they were training corpus in systems of pattern recognition applied to the genome.

From DNA to Gene Visualization

In certain sequence files the position of genes are within the sequence but our goal is to be able to graphically visualize genes on a molecule.

6.6 Protein Visualization [8]

A protein is a sequence of amino acids. The proteins adopt, because of their molecular structure, a three-dimensional conformation. These molecular sets are directly related to genes. It is thus essential to be able simultaneously to visualize genes and corresponding proteins.

6.7 From Stereo-Workstation to Virtual Reality Plate-Form

In the case of a standard graphical workstation, the user interface can be included in the graphical window of the application itself and often this is a good solution for the ease of use. But in the case of a platform of virtual reality, for example the HoloBench (cf. Figure 15) which is a semi-immersion environment, integrating a small 2d menu in the stereoscopic scene is not possible. This problem is even more critical in full-immersion environments (cf. Figure 15) such as the CAVE (Cave Automatic Virtual Environment)

Figure 15: HoloBench© and CAVE© plate-forms

The solution to this problem is generally to create a stereoscopic 3d menu, however, this solution greatly diminishes the full interaction potential of a stereoscopic scene, especially if the application environment allows a full-immersion

Users need to interact with a scene naturally, a goal which can be achieved if the interface is dissociated from the scene display. For example, one technical solution is the multi-display which locates the control of the interface at a workstation while displaying the scene on the screens of another workstation or platform. 

The interface can then more easily evolve by the incorporation of new multi-modal functions such as menu access through vocal commands [3] in order, for example, to change levels of representation, points of view, data extraction parameters, etc.

Immersion-based navigation [1] makes it possible to eliminate all the classical input devices (3d mouse, Joystick, Keyboard, etc.) used for navigation within a virtual scene. For instance, with a tracking system using stereoscopic glasses, it is enough to perform head movements in order to navigate in the virtual scene (cf. Figure 16).

Figure 16: Shutter-Glass© + Headphone© + Tracker© (CrystalEyes, Inc.)

Gesture interactions [10] can be very useful when the user wants to manipulate, to describe or point to a molecule or to a part of a molecule. It is much more ergonomic to consider the molecule as being a single object rather than representing the problem of exploring its structure as being a navigational one. 

A data glove would be perfectly appropriate for this type of design. One could also use a device with tactile feedback, as shows it the Figure 17.

Figure 17: CyberGrasp© with feedback 

(Virtual Technologies, Inc.)

7. Conclusion

This paper described a software framework for 3d modeling and stereoscopic visualization of scientific information dealing with genomic data. This work is based on close cooperation between biologists and computer scientists because, as we've shown in this paper, its through our work together that we have designed a first version of LIMSI's ADN_Viewer and are starting to augment its functionalities. Biologists on the Orsay campus are currently using the Viewer to analyze the 3d structures and folds of DNA taken from different organisms. In the very near future, the tool will become a part of LIMSI's new virtual reality platform and biologists will be able to access it from their standard graphical workstation. 

8. References

[1] P. Bourdot and M. Dromigny and L. Arnal", "Virtual Navigation Fully controlled by Head Tracking", in proc. ofinternational scientific symposium on Virtual Reality, June 1999, Laval, France.

[2] E.S. Shpigelman and E.N. Trifonov and A. Bolshoy, ?CURVATURE~: software for the analysis of curved DNA", CABIOS journal, Oxford University Press, 1993, pp. 435-440.

[3] P. Bourdot and M. Krus and R. Gherbi, ?Cooperation between Reactive 3D Objects & a Multimodal X Window Kernel for CAD?, in Multimodal Human-Computer Communication, Lecture Notes in Artificial Intelligence 1374, Subseries of Lecture Notes in Computer Science, H. Bunt & RJ. Beun & T. Borghuis Eds. Springer-Verlag, 1998, pp 188-212.

[4] L. Sicaud and R. Simermann and R. Gherbi, "Algorithmes de segmentation et de calcul de courbures~: application au génome",

Technical Report, LIMSI-CNRS, to appear.

[5] P. Pasero, "L'organisation du chromosome eucaryote et ses implications dans le contrôle de l'activité génique et la transmission des patrons d'expression", PhD thesis in cellular Biology and Microbiology, University of Aix-Marseille II, Luminy", 1993, France.

[6] M. Roux-Rouquié and M. Marilley, "Modeling of DNA local parameters predicts encrypted architectural motifs in Xenopus laevis ribosomal gene promoter", 2000, Nucleic acids research.

[7] M. Marilley and P. Pasero, "Common DNA structural features exhibited by eukaryotic ribosomal gene promoters." Nucleic Acids Res. 1996 Jun 15;24(12):2204-11

[8] R. Sayle, "RasMol : software tool for protein visualization", http:://www.chemie.fu-berlin.de/chemnet/use/rasmol.html, 1995.

[9] Silicon Graphics, "OpenGL Reference Manual",

http://shiva.missouri.edu:88/SGI\_Developer/OpenGL\_RM/6300.toc\#X",Silicon Graphics publication.

[10] A. Braffort and R. Gherbi and S. Gibet and J. Richardson and D. Teil (Eds.), "Gesture-Based Communication in Human-Computer Interaction", Lecture Notes in Artificial Intelligence, number 1739, Springer, 1999.

[11] JM. Lackie and JAT Dow, ?The dictionary of cell and molecular biology?, Academic Press,London, 1999.

[12] J-P. Boden and J-N. Cloarec and all, "Biologie Terminale D", collection Tavernier, Bordas editor, 1989.

[13] P. Fuchs, "Les interfaces de la Réalité Virtuelle", AJIIMD", 1996.

[14] H. Rheingold, "Virtual Reality", Touchstone Books, 1992.

About the authors

Rachid Gherbi is an associated professor at LIMSI (Engineering Science laboratory of National Center for Scientific Research) and Computer Science Department of Paris-Sud University. His main interests are in the fields of computer vision and 3d modeling, virtual and augmented reality, and pattern recognition focused on applications in human-computer interaction and bioinformatics.

Joan Hérisson is a master student in computer science at Paris-Sud University. He will start a PhD work, at LIMSI, on virtual reality and, more particularly, the management of complex and rich graphical data for bioinformatic applications in genomics.