


\section*{Introduction}
Multiple Sequences Alignment (MSA) plays a key role in modern bioinformatics as cornerstone tool for biological studies such as sequence analysis, evolutionary studies, comparative genomics... All these approaches have in common to use MSAs as primary source of integration of any type of data (structural, functional and even cellular, tissular or developmental) in the framework of the closeness of the aligned sequences. 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}.

As a MSA is both the main data source for some applications (phylogeny, motif discovery, etc ...) and the host for mapping data coming from diverse studies, it may be seen as a hub where information from different nature and sources meet.
In both cases, a fruitful MSA exploitation ensuring a high quality data deciphering and information mapping 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. 
 
But MSAs are not static objects. Even if, formly, a set of aligned sequences constitutes a multiple sequence alignment, in real life there are as many different aligments as undertaken studies types for a same set of aligned sequences. Indeed, a study may need a specific sequence ordering, a different sequence clustering for example. Several solutions for aligning residues may also exists leading to different alignments. 
%OP: je ne suis pas sûr que ces phrases, en l'état, soient utiles pour justifier ORDALIE. Si j'ai bien compris l'idée c'est de mettre en avant un ou les pints forts et différents d'ORDALIE par rapport aux autres MSA éditeurs???
Numerous programs for MSA visualisation, edition or manipulation do exist \cite{listmsatools, soft:jalview2} aend are still developped \cite{soft:seqtools, soft:aliview}. They usually handle only one instances of the current alignment at a time and their associated alignment editor facilities are usually slow or hard to use. 
//
We present here ORDALIE (ORDered ALignment Information Explorer), a workbench dedicated to the analysis and exploration of the informational content of a MSA, i.e. to give an access to the global informational content attached to a given MSA. ORDALIE manages, manipulates and stores several instances of an alignment, hereafter called "snapshots", and their associated features data if any. It also provides several tools to extract and decipher the intrinsic alignment information. 

\section*{The ORDALIE core elements}
\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 of an alignment and their associated features. 
The "ordalie" table contains settings parameters saved at exit allowing the user to find 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 residue sequence. 
Upon loading of a new alignment file, ORDALIE creates a first snapshot as being a read-only copy of this alignment and stored "original alignment". This table will contain all snapshots subsequently created along with their name and description.
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" couple this two tables.
The "clustering" and "cluster" tables define a given clustering attached to a snapshot with its name, the \textbf{method and residue eones} used to compute it, and the resulting clusters with their names respectively. 
The set of sequences defining a given cluster is available through the "ln\_seqali\_clluster" link table.
The "colmeasure" and "colscore" tables correspond to conservation computations (column measurements) with their name and used method, and the conservation groups with name, value for each column of the group respectively. 
%OP: pas clair
The conservation score for a given cluster is available through the link table "ln\_cluster\_colscore".
Finally, the "annotation" table contains all information relative to annotation the user adds to a given snapshot.
The ORDALIE (.ord file extension) consists in a database dump.

\subsection*{Snapshot Management}
ORDALIE reads and writes alignments in MSF, Fasta, Clustal, MACSIMS/XML file formats and the specific ORDALIE file format. Once loaded, ORDALIE allows to cut, copy, paste or displacement of sequences. Empty sequences names ("separators") can be inserted or removed in order to create user-defined groups outside the "Clustering" tool. Sequences can be imported and aligned against the current set of sequences. The whole or parts of the MSA can be printed for publication issues.

\subsection*{Snapshot Editing}
In order to perform fast snapshot editing, we develop a dedicated Tk widget written in C for performance issues. The "Editor" functionnalities are based and extend the 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 sequence unlocking. The residues coloring scheme is adapted from SeqLab and can be changed by the user. After edition, the user can save or discard the modified snapshot.

\subsection*{Features}
In ORDALIE, a feature is a position dependent sequence characteristic. It may define the extend of a PFAM domain, transmenbrane regions, PROSITE sites (the former features examples are provided by the MACSIMS program output file \cite{soft:macsims}) as well as exon mapping for example. 
A feature is defined 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}, or 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 main ORDALIE window 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 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. Any sequence name can be searched through a text box placed below the sequences names. The matching name is then positionned at the top of the names list. Below the amino acid sequences, the coordinates of the current position of the mouse pointer are written both in global alignment and local sequence coordinates systems. A ruler gives the columns positions. 
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\textbf{ being stacked one onto the other}. 
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), 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 alignment 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 NEXUS 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 branches, display bootstrap values, show nodes above a bootstrap threshold, change leaves labelling, color leave according to their group 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 alignment allow the user to estimate the evolution difference 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. 
ORDALIE provides a clustering tools allowing clustering sequences on all or parts of the columns. The user should choose one or combine 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 algorithmms that define the number of clusters are taken from the Cluspack package. The available methods are:  hierarchical clustering/secator \cite{secator}, kmeans 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 effect and reveals zones of functional interest in the sequence. When narrowing the focus of the conservation analysis at the group level, the outcoming information may enlight the clustering choice, for example, sequences clustered according to medohiles, 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 displays the two most conserved groups of columns in the snapshot. Indeed, the conservation scores are clustered using a hierarchic clustering and the ``secator'' program to determine the groups. The two groups having the highest mean, 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" "BILD" \cite{liu, liu2, soft:clustalx, bild}. The ``Mean Distance'' is the method implemented in the ClustalX program, the ``Vector Norm'' is a home-made method, the ``BILD'' method is a Bayesian-based method. The "Threshold" method is a special case and 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 useing 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 same two global conservation groups and shows 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 trials done and the user saves the only relevant ones.

\subsection*{3D viewer}
The main interest of the ``3D Viewer'' tool resides in its ability to map features to a 3D structure. Contextualizing a feature with 3D notions like surface accessibility, 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 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 represents the current snapshot as a white and grey pixel map onto which one or more features can be drawn. This gives a schematic representation of the features distribution along the alignment. The overview can be scaled and printed.
\\
The "Search" tool allows to find motifs inside the alignment. The search motif syntax follows the FindPattern syntax \cite{soft:gcg}. The pattern may be degenerated. Occurences of the motif appear in red in the sequence window.
\\
The "Fetch Information" tool will request the UniProt and Refseq databases \cite{db:uniprot, db:refseq} using the sequence IDs to retrieve relevant information, like organism, description, lineage, etc...


\section*{Conclusion}
By embedding a database system along with alignment manipulation and exploration tools, ORDALIE provides the ability to explore several hypothesis in alignment analysis thanks to the snapshots feature. ORDALIE ensures \textbf{a.persistence of data deciphered} from MSA analysis.  
 The interconnected tools (clustering, phylogenetic tree, conservation computation, 3D structure mapping) allow a broad variety of information mining for alignment exploitation. The ORDALIE interface has been designed to be intuitive and simple 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.






% 06 58 93 57 21
% adrien adam
% atchome bardage

% hyani garbari assistance

 %covacic ernoldsheim
 %arc home
