




\section*{Introduction}
Multiple sequences alignments (MSAs) play a key role in modern bioinformatics as becoming cornerstones of several types of investigations like protein family analysis, evolutionary inferred studies or comparative genomics. All these techniques have in comon to use MSAs as primary source of information. MSAs became also the support for data interpretation in studies like genomic variation pathogenicity inference where insertion/deletion or amino acids changements can be analysed in the frame of family or sub-family residues conservation. 
In both cases of MSAs exploitation, ensuring a high degree of quality of data deciphering or mapping information is directly dependent on the accuracy of the alignments. It should be stressed here that although the research on algorithms dedicated to align sequences is still intensive and the outcoming softwares are more and more accurate, the need of manual inspection, curation and even editing of alignments is still necessary. 
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. 
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. 
Numerous programs for MSA visualisation, edition or manipulation do exist \cite{listmsatools, soft:jalview2}. They usually handle only one instances of the current alignment 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 information sphere attached to a given MSA. ORDALIE manages, manipulates and stores instances of alignments, 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 XXX. ORDALIE takes advantage of this underlaying database to store snapshots of alignments 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 (length, molecular weight, isoelectric point, ...)
The "seqfeat" table is used to store features data mapped onto the residue sequence. 
The "snapshot" table conains all the alignments created so far, with their name and descriptions. Upon loading of a new alignment file, ORDALIE makes a read-only copy of this alignment, stored as the "original alignment". 
The "seqali" table records sequences as they appear in the current alignment. 
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 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 consrvation groups with name, value for each column of the group respectively. 
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*{Alignement Management}
ORDALIE reads and writes alignments in MSF, Fasta, ClustalW, MACSIMS/XML file formats and the specific ORDALIE file format. Once loaded, ORDALIE allows standard alignment edition, like cut, copy and paste of sequences. Empty sequences names ("separators") can be inserted or removed in order to create user-defined groups outside the "Cluster" tool. The whole or parts of the MSA can be printed for publication issues.

\subsection*{Alignment Editing}
In order to perform fast alignment 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. By default, the user can only insert/romove 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 SeqLb and can be changed by the user. After edition, the user can save or discard the modified aligment. 


\subsection*{Features}
In ORDALIE, 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 alignment 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 design 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 at the left, and the amino acid sequences at the right. A given 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 aminoacid 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 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 sttistics. 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 must choose one or more criterias and one clustering method. The available criterions 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, kmeans clustering with DPC (Dendity Point Clustering), and mixture model clustering with AIC or BIC criteria. The special "Life Domain" criterion clusters sequences into "Eukaryota", "Archaea", "Bacteria", "viruses" or "unknown" according to the sequence lineage. The clustering can then be saved, and retrieved later.

\subsection*{Conservation}
The sequence conservation constitutes a fingerprint of the evolution pressure effect and reveals zone of interest in the sequence.
Many algorithms exist to compute conservation \cite{valdar, johansson}. ORDALIE implements five methods "Threshold" "Liu" "Mean Distances" "Vector Norm" "Multi" "BILD". The "Threshold" method makes a simple counting of conserved residues and shores them in three groups : 100% conserved, >80% conserved and >60% physicochemical conserved useing the aminoacids groups PAGST, DEQN, KRH, FYW, ILMV, and C. The "Mean Distance" method is used in the ClustalX program. 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 three global conservation groups and shows also the main conserved columns in each seuence clusters. The conservation scores can be plotted under the alignment columns by setting the "Show Score" ckeckbox. ORDALIE stores temporarily all trials done and the user saves the only relevant ones.


\subsection*{3D viewer}
If a sequence name refers to a PDB ID \cite{db:pdb}, the correstonding 3D structure coordinates file is automatically downloaded and processed, can be displayed in the "3D vieuwer" tool. By default, for each downloaded structure, ORDALIE builds three representations : a full atoms model, a C$\alpha$ trace model and a flfat 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 teh 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 a.persistence of data deciphered from MSA analysis.  
 The interconnected tools (clustereing, 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.






