


\section*{Introduction}
Multiple Sequences Alignments (MSAs) play a key role in modern bioinformatics as cornerstones tools for diverse biological studies such as sequence analysis, evolutionary studies, comparative genomics... All these approaches have in common to use MSAs as primary source of integration, allowing the retrieval of several kind of data (structural, functional and even cellular, tissular localisation or developmental stage) in the framework of the closeness of the related aligned sequences.F 
Recently, MSAs became a major support for the study of inter-individual genomic variation pathogenicity providing the best evaluation scoring systems of potential disease-causing insertion/deletion or amino acids replacements \cite{polyphen2,soft:sift}.
All this constatations yield to new requirements for programs handling MSAs. 

Being considered as a main data source or a data mapping environment, a fruittful MSA exploitation is directly dependent on the accuracy of the alignments. Although the research on algorithms dedicated to align sequences is still intensive and the outcoming softwares are more and more accurate \cite{book:julie, review:bawono, review:chatzou, soft:m2align}, the need of manual MSA inspection, curation and editing is still necessary.
Furthermore MSA as data source are usually customized depending on the targeted study. For example the sequences can be clustered differently, and the embedded features may also .
This appeals to maintain in parallel several instances of a same alignment between which the user can swap.

Numerous programs for MSA visualisation, edition and manipulation already exist \cite{listmsatools, soft:jalview2} and are still being developped \cite{soft:seqtools, soft:aliview} displaying all different strengths and weaknesses.
//
We present here ORDALIE (ORDered ALignment Information Explorer), a workbench dedicated to the analysis and exploration of the informational content of a protein MSA.

ORDALIE has been designed around three main ideas : a powerfull set of editing capabilities, the ability to annotate sequences with on-the-fly computed or external featurese and a mechanism to handle several instances of a given alignment, hereafter called ``snapshots''.
The ORDALIE ability to manage, manipulate and store several snapshots and their associated features data combined with the provided associated tools give the biologist a frame to perform a transversal analysis of the alignment.
Finally, as bioinformatics tools are nowadays used in all laboratories, the graphical user intece of ORDALIE benefits a special care.


\section*{The ORDALIE core components}
\subsection*{The database}
The core of ORDALIE is build around a in-memory SQLite database \cite{soft:sqlite} which scheme is given in figure \ref{fig-dbscheme}. ORDALIE takes advantage of this underlaying database to store snapshots and their associated features.

The "ordalie" table contains settings parameters (colors, font size, ...) saved on exit allowing the user to recover the same state when launching ORDALIE again. 
The "seqinfo" table contains sequence information that are not linked to aminoacids positions (sequence length, molecular weight, isoelectric point, ...).
The "seqfeat" table is used to store features data mapped onto the aminoacids sequence. 
Upon loading of a new alignment file, ORDALIE creates a first snapshot as being a read-only copy of this alignment and it is stored as "original alignment". 
The "seqali" table records the amino acid sequences as they appear in the snapshots.
A link table "ln\_snapshot\_seqali" binds a given set of sequences to a given snapshot.
Accordingly, the "featali" table stores features attached to aligned sequences in a given snapshot. A link table "ln\_seqali\_featali" couples this two tables.
The "clustering'' table defines a clustering with its name, residue zones used to compute it and the algorithm used, and the ``cluster'' table stores the resulting clusters with their names. 
The "ln\_seqali\_clluster" link table defines the set of sequences belonging to a given cluster.
The  parameters for the computation of the residue conservation along the columns (columns scores measurements), i.e. name and used method used, are stored in the ``colmeasure'' table while the column scores themselves for each cluster are stored in the ``colscore'' table.
The table "ln\_cluster\_colscore" makes the cluster ans columns scores linkage.
Finally, the "annotation" table contains all information relative to annotation the user added to a given snapshot.

The ORDALIE type file (.ord file extension) consists in a database dump.


\subsection*{Snapshot Management}
ORDALIE reads and writes alignments in MSF, Fasta, Cl
ustal, MACSIMS/XML file formats and the specific ORDALIE file format. Once the alignment is loaded, the user can create several instances of thsi alignment, hereafter called ``snapshot''. The user can navigate between snapshots and modify or delete them.

The user can cut, copy, paste sequence(s) inside a snapshot. Empty sequences names (called "separators") can be inserted or removed in order to create user-defined clusters outside the "Clustering" tool (see below). New equences can be imported as FASTA type sequences. Sequences can be aligned or re-aligned against the current set of sequences of the snapshot using the DDBJ MAFFT web service \cite{soft:mafft}. The whole or parts of a snapshot can be printed for publication issues.


\subsection*{Snapshot Editing}
Manual curation remains an important task in order to imrpove the global alignment quality. We develop a dedicated Tk widget written in C for performance issues allowing fast snapshot edition. The "Editor" functionnalities are based but extend the old but famous SeqLab editor \cite{soft:seqlab} that was part of the GCG Wisconsin package \cite{soft:gcg}.
 By default, the user can only insert/remove gaps inside one or several sequences. Options for grouping/ungrouping sequences and removing columns of gaps are provided. Amino acids may be edited after unlocking sequence. The residues coloring scheme is adapted from SeqLab and can be customized. After edition, the user can save or discard the modified snapshot.

\subsection*{Features}
In ORDALIE, a feature is defined as a position dependent sequence characteristic like the extend of a PFAM domain, a transmenbrane regions, PROSITE sites, exons limits for example.
%lm (the former features examples are provided by the MACSIMS program XML output file \cite{soft:macsims}) as well as exon or point mutation mapping.
A feature is specified by the sequence(s) it applies to, a start and stop position, a color, an associate score, a note, a coordinates system ("global" for snapshot position or "local" for sequence relative position).
Features are imported into ORDALIE through the Macsims program XML output file \cite{soft:macsims}, by using a dedicated feature file format, or manually defined using the "Feature tool". With this tool, features can be created, modified or deleted.


\section*{The ORDALIE user interface}
The ORDALIE interface has been designed to be intuitive and easy to use for non-bioinformatician users. The ORDALIE emainwindow is divided in three parts. 
The top part contains the menu bar, the icons bar which are shortcuts to most usefull menu items, and the snapshot management bar, allowing snapshot selection, creation and deletion. 
The middle part of the window contains the sequences names list on the left and the amino acid sequences on the right. Sequences names can be searched through a text box placed below the sequences names. The first matching name is then positionned at the top of the names list. Below the amino acid sequences, the current position of the mouse pointer are shown both in global alignment and local sequence coordinates systems. A ruler gives the columns positions attached to a horizontal slider.
The bottom part of the window hosts by default the on/off buttons for the available features. There is one button per available feature. The user can display several features at the same time, the features being stacked in the order they are switched on. 
When calling a tool, the features buttons are replaced by the control panel of the tool. Each tool has its own control panel (see below for a brief description), and leaving the tool restores the features buttons.


\section*{The ORDALIE associated Tools}
\subsection*{Trees}
ORDALIE builds phylogenetic trees based on all or parts of the aligned sequences, and all or parts of the snapshot columns. Based upon the user selection, ORDALIE computes a distance matrix using identity percentage, and then processes the distance matrix by the FastME program \cite{soft:fastme} using default parameters. Although likelihood-based trees are more reliable, the speed and reliability of FastME is enough to have a first insight into the protein phylogeny. The robustness of the tree nodes can be assessed through bootstrap statistics. The user can also import a pre-computed tree in Newick format.
The computed or imported tree is then displayed in a dedicated window. The tree can be viewed as a dendrogram or as a radial tree. The user can re-root the tree, swap nodes, display bootstrap values, show nodes above a bootstrap threshold, change leaves labelling, color leave according to their cluster or their life domain, print the tree and more. In the drawing area a contextual menu allows scaling of the tree and rotation of a radial tree.
The ORDALIE ability to build tree on parts of the snapshot allows the user to estimate the evolution differences between domains of the protein for example.

\subsection*{Clustering}
Sequence clustering is a tool that may enlight differences between sequences according to a given criteria. 
The ORDALIE clustering tool can be applied to all or parts of the columns. The user should choose one or several numerical criterias and one clustering method. 
The available criterias are identity percentage, isoelectric point, sequence length, hydrophobicity and aminoacid composition. The clustering algorithms along with criterias to automatically define the number of clusters are taken from the Cluspack package. The available methods are:  hierarchical clustering/secator \cite{secator}, k-means clustering with DPC (Density Point Clustering) \cite{dpc}, and mixture model clustering with AIC or BIC criteria \cite{mixturemodel, aic, bic}. 
The special "Life Domain" criterion clusters sequences into "Eukaryota", "Archaea", "Bacteria", "Viruses" or "unknown" according to the sequence lineage. This lineage is part of the Macsims/XML information file or can be retrieved by ORDALIE.

All computed clustering can then be saved and retrieved later.

\subsection*{Conservation}
The sequence conservation constitutes a fingerprint of the evolution pressure effects and reveals zones of functional interest in the sequence. When narrowing the focus of the conservation analysis at the cluster level, the outcoming information may enlight the clustering choice, for example, sequences clustered according to mesohiles, psychrophile and therophiles will display a different pattern than sequences clustered according to phylogenetic ranks.

Many algorithms exist to compute residues conservation or dispersion \cite{valdar, johansson}. One of the interesting feature of ORDALIE is that it not only computes the conservation scores along the snapshot columns, but it automatically defines and displays the two most conserved groups of columns in the snapshot. Indeed, the conservation scores are clustered using a hierarchic clustering and the ``secator'' programs. The two groups having the highest mean conservation score corresponding to the two most conserved groups of residues are then displayed with a black and dark gray background respectively.

ORDALIE implements six methods to compute residue conservation: "Threshold", "Liu", "Mean Distances", "Vector Norm", "Multi" and "BILD" \cite{liu, liu2, soft:clustalx, bild}. The ``Vector Norm'' is a home-made method. The "Threshold" method makes a simple counting of conserved residues inside a column. The columns are then partitionned into three groups: 100\% conserved, >80\% conserved and >60\% physicochemical conserved using the aminoacids groups PAGST, DEQN, KRH, FYW, ILMV, and C. 

Conservation computation can be done either considering the whole set of sequences as one group ("Global" option) or taking the sequence clustering into account. In the later case, ORDALIE outputs the first two global conservation groups and also the most conserved columns in each seuence clusters. The conservation scores can be plotted under the snapshot columns by setting the "Show Score" ckeckbox. ORDALIE stores temporarily all computation trials until the user saves the most relevant ones.

\subsection*{3D viewer}
The main interest of the ``3D Viewer'' tool resides in its ability to map snapshot features to a 3D structure. Contextualizing a feature within 3D structure aspects like molecular surface accessibility, spatial closeness to other features, etc ... is greatly valuable to understand a feature function.

In ORDALIE, if a sequence name refers to a PDB ID \cite{db:pdb}, the corresponding 3D structure coordinates file is automatically downloaded, processed and can be displayed in the ``3D viewer'' tool. By default, ORDALIE builds three 3D models representations: a full atoms model, a C$\alpha$ trace model and a flat ribbon model. Models rotation and translation follow a mouse virtual trackball. All available features can be mapped on a model. After selecting a structure and a model, the user can map two features onto the model. A model builder allows to create customized model representation and coloring.

\subsection*{Other tools}
The ``Overview'' tool creates a schematic representation of the current snapshot as a white and grey pixel map onto which one or more features can be drawn. This gives a an overview of the features distribution along the snapshot. The overview can be scaled and printed.
\\
The ``Search'' tool allows to find motifs inside the aligned sequences. The search motif syntax follows the FindPattern program syntax \cite{soft:gcg}. The pattern may be degenerated. Occurences of the motif appear in red in the sequence window.
\\
The ``Fetch Information'' tool requests the UniProt and RefSeq databases \cite{db:uniprot, db:refseq} using sequence IDs to retrieve relevant information, like organism name, description, lineage, etc...


\section*{Conclusion}
By embedding in a same program a database system along with alignment manipulation and exploration tools as well as a complete feature definition and mapping, ORDALIE provides a framework to explore several alignment analysis hypothesis by considering several contexts (thermoophilicity, protein interaction networks, protein sub-families, ...). The ORDALIE file type (a dump of the internal database) ensures a.backup and restore session capability.
 The interconnected tools (clustering, phylogenetic tree, conservation computation, 3D structure mapping) allow a broad variety of information mining for alignment exploitation. Finally, the ORDALIE interface has been designed to be intuitive and user-friendly making ORDALIE accessible to non bioinformaticians users.


\section*{Availability and Requirements}
ORDALIE is written in Tcl/Tk \cite{soft:tcltk}, version 8.6.6. The alignment editor Tk widget (Biotext) is written in C for performances issues and is included in the ORDALIE distribution. Installers and binaries are provided for Windows, Mac OS X and Linux as well as source code and documentation at http://www.lbgi.fr/ordalie. 
ORDALIE is an open-source program and is distributed under the LGPL licence.

