

%\subsubsection{Using genes names provided by annotation tools}
%
%Instead of using the sequences predicted by annotation tools, we can
%try to use the names associated to these sequences, when available.
%The basic idea is thus to annotate all the sequences using a given
%software, and to consider as core gene each sequence whose name can
%be found in all the genomes.
%Two annotation  techniques will be used in the remainder of this article,
%namely DOGMA and NCBI. 
%
%
%It is true that the NCBI annotations are of varying 
%qualities, and sometimes such annotations are totally erroneous. As stated before, it is due to the
%large variety of annotation tools that can been used during each
%sequence submission process. However, we also considered it in this
%article, as this database contains human-curated annotations. To say this
%another way, DOGMA automatic annotations are good in average, while
%NCBI contains very good human-based annotations together with very badly
%annotated genomes. 
%Let us finally remark that DOGMA also predict the locations of
%\textit{ribosomal  RNA (rRNA)}, while they are not provided in 
%gene features from NCBI. Thus core genomes constructed on NCBI
%data will not contain rRNA.

We now investigate core and pan genomes design
using each of the two tools separately, which will constitute the second
approach detailed in this article. From now on we will consider annotated
genomes: either ``genes features'' downloaded from the NCBI, or the
result of DOGMA.

%\subsubsection{Names processing}
%
%As DOGMA is a deterministic annotation tool, when a given gene
%is detected twice in two genomes, the same name will be attached
%to the two coding sequences: DOGMA spells exactly in the same manner
%the two gene names. So each genome is replaced by a list of gene 
%names, and finding the core genes common to two genomes simply 
%consists in intersecting the two lists of genes. The sole problem
%we have detected using DOGMA on our 97 chloroplasts is the case
%of the RPS12 gene: some genomes contain RPS12\_3end
%or RPS12\_5end in the DOGMA result. We have manually 
%considered that all these representatives belong to the same gene,
%namely to RPS12.
%
%Dealing with NCBI names is more complicated, as various annotation
%tools have been used together with human annotations, and because there is
%no spelling rule for gene names. For instance, NAD6 mitochondrial gene is
%sometimes written as ND6, while we can find RPOC1, RPOC1A, and RPOC1B in 
%our chloroplasts. So if we simply consider NCBI data without 
%treatment, intersecting two genomes provided as list of gene names often 
%lead to duplication of misspelled genes. Automatic names homogenization is thus required
%on NCBI annotations, the question being where to draw the line 
%on correcting errors in the spelling of genes ? In this second approach,
%we propose to automate only obvious modifications like putting all names
%in capital letters and removing useless symbols as ``\_'', ``('', and ``)''.
%Remark that such simple renaming process cannot tackle with the situations of NAD6 or 
%RPOC1 evoked above. To go further in automatic corrections requires
%to use edit distances like the Levenshtein one, however such an use will
%raise false positives (different genes with close names will be homogenized). 
%To solve this problem, a compromise that reduces the number of false positives, by considering the similarity between DNA sequences of genes having similar names, will be detailed in the third approach.
%
%At this stage, we now consider that each genome is mapped to a list of gene
%names, where names have been homogenized in the NCBI case.



%\subsubsection{Core genes extraction}
%
%% The goal of  this stage is to extract maximum core genes from sets of
%% genes.  To find core genes, the following methodology is applied.
%% 
%
%%\subsubsection{Intersection Core Matrix (\textit{ICM})}
%
%To extract  core genes, we  iteratively collect the maximum  number of
%common  genes   between  genomes,  therefore   during  this  stage
%an \textit{Intersection  Core Matrix}  (ICM) is built.   ICM is  a two
%dimensional symmetric matrix where each row and each column correspond
%to   one   genome.   Hence,   an   element   of   the  matrix   stores
%the  \textit{Intersection Score}  (IS):  the cardinality  of the  core
%genes   set  obtained   by  intersecting     the two genomes. 
%%Maximum  cardinality results in selecting the  two genomes having
%%the maximum score. 
%Mathematically speaking, if we have $n$ genomes in
%local database, the ICM is an $n \times n$ matrix whose elements
%satisfy: 
%\begin{equation}
%score_{ij}=\vert g_i \cap g_j\vert
%\label{Eq1}
%\end{equation}
%\noindent where $1 \leq i \leq n$, $1 \leq j \leq n$, and $g_i, g_j$ are 
%genomes. The  generation of a new  core genome depends  obviously on the
%value  of the  intersection scores  $score_{ij}$. More  precisely, the
%idea is  to consider a  pair of genomes  such that their score  is the
%largest element in the ICM. These two genomes are then removed from the matrix
%and the  resulting new  core genome is  added for the  next iteration.
%The ICM is then updated to take into account the new core genome: new IS
%values are computed for it. This process is repeated until no new core
%genome can be obtained.
%
%We  can observe  that  the ICM  is relatively  large  due to  the amount  of
%species. As a consequence, the  computation of the intersection scores is
%both  time and  memory consuming.  However,  since ICM  is obviously a  symmetric
%matrix we can reduce the  computation overhead by considering only its
%triangular  upper part.  The  time complexity  for this  process %after
%%enhancement 
%is thus $O(\frac{n.(n-1)}{2})$.  Algorithm~\ref{Alg1:ICM}
%illustrates the construction  of the ICM matrix and  the extraction of
%the  core  genomes, where  \textit{GenomeList}  represents the  database
%storing all genomes  data. At each iteration, this algorithm computes the maximum
%core genome with its two  parents (genomes).
%
%% ALGORITHM HAS BEEN REWRITTEN
%
%\begin{algorithm}[H]
%\caption{Extract Maximum Intersection Score}
%\label{Alg1:ICM}
%\begin{algorithmic} 
%\REQUIRE $L \leftarrow \text{genomes sets}$
%\ENSURE $B1 \leftarrow \text{Max Core set}$ 
%\FOR{$i \leftarrow 1:len(L)-1$}
%        \STATE $score \leftarrow 0$
%	\STATE $core1 \leftarrow set(GenomeList[L[i]])$
%	\STATE $g1 \leftarrow L[i]$
%	\FOR{$j \leftarrow i+1:len(L)$}
%	        \STATE $core2 \leftarrow set(GenomeList[L[j]])$
%		\STATE $core \leftarrow core1 \cap core2$
%		\IF{$len(core) > score$}
%                  \STATE $score \leftarrow len(core)$
%		  \STATE $g2 \leftarrow L[j]$
%                \ENDIF
%	\ENDFOR
%	\STATE $B1[score] \leftarrow (g1,g2)$
%\ENDFOR
%\RETURN $max(B1)$
%\end{algorithmic}
%\end{algorithm}
%
%For complete core trees based either on NCBI names or on DOGMA ones, (see \url{http://members.femto-st.fr/christophe-guyeux/}).
%%\color{red} The second approach is dependent on gene names spelling. When realizing simple homogenization of names provided by NCBI, we miss core genes which have slightly different name formats. So that, good annotation tool is highly required. \color{black} 
%
%%\subsection{Features visualization}
%%The last stage of the proposed pipeline is naturally to take advantage
%%of the produced core and pan genomes for biological studies. As
%%this key stage is not directly related to the methodology for core
%%and pan genomes discovery, we will only outline a few tasks that
%%can be operated on the produced data.
%%
%%\begin{figure}
%%\centering
%%\includegraphics[scale=0.215]{tree}
%%\caption{Part of a core genomes evolutionary tree (NCBI gene names)}
%%\label{coreTree}
%%\end{figure}
%%
%%Obtained results may be visualized by building a core genomes evolutionary tree. 
%%% All core  genes generated  represent  an important information  in the  tree,
%%% because they  provide ancestor information of two  or more
%%% genomes. 
%%Each  node in this  tree represents a chloroplast  genome or
%%a predicted core, as depicted in Figure~\ref{coreTree}. In this 
%%figure, nodes labels are of the form 
%%\textit{(Genes number:Family name\_Scientific name\_Accession number)},
%%while an edge is labeled with the number of
%%gene loss when compared to its parents (a leaf  genome or  an intermediate  
%%core  genome). Such numbers can answer questions like:  
%%how many genes are different between two  species? Which functionality has
%%been lost between an ancestor and its children ? For complete core trees
%%based either on NCBI names or on DOGMA ones, see supplementary data.
%%
%%
%%
%%A second application of such data is obviously to build accurate phylogenetic   
%%trees, using tools like
%%PHYML\cite{guindon2005phyml} or 
%%RAxML{\cite{stamatakis2008raxml,stamatakis2005raxml}. 
%%Consider a set of species, the last common core genome in the core tree 
%%contains all the genes shared in common by these species. These genes may be
%%multi aligned to serve as input of the phylogenetic tools mentioned above.
%%An example of such a phylogenetic tree on core 58 (NCBI cores tree, see
%%supplementary data) is provided in Appendix~\ref{philoTree}. Remark that, in
%%order to constitute a relevant outgroup, we have simply blasted each gene 
%%of this core on a chosen \emph{Cyanobacteria}.
%%
