



%\subsection{Implementation}
%\label{sec:implem}
%All the  algorithms detailed in this article have  
%been implemented using  Python~2.7 on a personal computer (Ubuntu~12.04 with 6~GiB memory,  quad-core Intel~i5 with  an operating  frequency of
%2.5~GHz). %All programs can be downloaded at \begin{color}{red} \url{http://......} \end{color}. 
%%genes  from large  amount of  chloroplast  genomes.
%
%%\begin{center}
%\begin{table}[H]
%\centering
%\caption{Type of annotations and execution time}\label{Etime}
%{%\scriptsize
%%\begin{tabular}{p{2.3cm}p{0.5cm}p{0.25cm}p{0.5cm}p{0.25cm}p{0.5cm}p{0.25cm}}%p{0.5cm}p{0.25cm}p{0.5cm}p{0.2cm}}
%\begin{tabular}{ccccccc}
%\hline\hline
% Method & \multicolumn{2}{c}{Annotation} & \multicolumn{2}{c}{Features} & \multicolumn{2}{c}{Exec. time (min.)} \\%& \multicolumn{2}{c}{Core genes} & \multicolumn{2}{c}{Bad genomes} \\
%~ & N & D & Name & Seq & N & D \\%& N & D & N & D \\
%\hline
%First approach & $\surd$ & - & - & $\surd$ & 1.7 & -\\% & ? & - & 0 & -\\[0.5ex]
%Second approach & $\surd$ & $\surd$ & $\surd$ & - & 4.98 & 1.52\\% & 28 & 10 & 1 & 0\\[0.5ex]
%Third approach & $\surd$ & $\surd$ & $\surd$ & $\surd$ & \multicolumn{2}{c}{$\simeq$3 days + 1.29} \\%& \multicolumn{2}{c}{4} & \multicolumn{2}{c}{1}\\[1ex]
%\hline
%\end{tabular}
%}
%\end{table}
%%\end{center} 
%
%%\vspace{-1cm}
%
%Table~\ref{Etime}  presents   the  annotation  type,
%execution time,  and the  number of core  genes  for  each proposed  method. The following
%notations have been used:  \textbf{N}  denotes NCBI and  \textbf{D} means  DOGMA,
%while \textbf{Seq}  stands for sequence. The  two first {\it Annotation} columns
%represent the algorithm used to annotate chloroplast genomes. The next two {\it
%Features} columns mean  the kind  of gene feature used to extract core
%genes: gene name, gene sequence, or  both of them. 
%
%It can be seen that
%almost all methods need low execution time  to extract core genes
%from the large set of chloroplast genomes. Only the third method requires
%more than one day of computation (about 3-4 days) for sequence comparisons. However,
%once the quality genomes are well constructed, it only takes 1.29~minutes to
%extract the core genes. Such low execution times allow us  to use these
%methods to extract all core genomes  on a personal computer. 
%The lowest execution time (1.52~minutes)
%is obtained with the second method using DOGMA annotations. 
%
%
%The second important computational factor is the amount of memory necessary for each
%methodology.   Table~\ref{mem}  shows  the  memory   usage  of  each
%method. In this table, the values are  presented in megabyte
%unit, while \textit{gV} means  geneVision~file~format. We can notice that
%the quantity  of required memory  is relatively low  for all methods,
%and is available  on any personal computer. The  different values also
%show that the gene features  method based on DOGMA annotations has the
%most   reasonable   memory   usage,   except  when   extracting   core
%sequences. The third method gives the lowest values if we already have
%the   ``quality   genomes'',   otherwise   it  will   consume   far   more
%memory. Remark that the  amount of memory  used by the third method also
%depends on the size of each genome.
%
%
%\begin{table}[H]
%\centering
%\caption{Memory usages for each methodology (in MB)}\label{mem}
%\tabcolsep=0.11cm
%{\scriptsize
%\begin{tabular}{p{2.5cm}@{\hskip 0.1mm}p{1.5cm}@{\hskip 0.1mm}p{1cm}@{\hskip 0.1mm}p{1cm}@{\hskip 0.1mm}p{1cm}@{\hskip 0.1mm}p{1cm}@{\hskip 0.1mm}p{1cm}@{\hskip 0.1mm}p{1cm}}
%\hline\hline
%Method& & Load Gen. & Conv. gV & Read gV & ICM & Core tree & Core Seq. \\
%\hline
%Gene prediction & NCBI & 108 & - & - & - & - & -\\
%\multirow{2}{*}{Gene Features} & NCBI & 15.4 & 18.9 & 17.5 & 18 & 18 & 28.1\\
%              & DOGMA& 15.3 & 15.3 & 16.8 & 17.8 & 17.9 & 31.2\\
%Gene Quality  & ~ & 15.3 & $\le$3G & 16.1 & 17 & 17.1 & 24.4\\ 
%\hline
%\end{tabular}
%}
%\end{table}
% 
% 
%\subsection{Results comparison}
%
%Method 2 has indicated to us that two genomes must be removed from the
%set of chloroplasts, namely \textit{Epifagus virginiana} (NC\_001568.1)
%and \textit{Cuscuta gronovii} (NC\_009765.1). The reason to
%be of this update is that (1) these chloroplastic genomes are non functional ones,
%and (2) considering them leads to a too small final core genome.
%Additionally, we have been forced to remove \textit{NC\_012568.1  Micromonas pusilla} 
%from the NCBI study, as its wrong annotations lead to an empty
%final core genome.
%
%The number
%of {\it  Core genes} in Table~\ref{Etime} represents the  amount of genes in  the last core
%genome (the core genes shared by all the chloroplasts). 
%%The main goal is to  find the maximum core genes that simulate
%%biological background of chloroplasts. 
%With  NCBI we obtained 28 genes for
%96   genomes, while DOGMA approach produces 10   genes for  the whole 97  genomes.
% However we will see that the distribution of  genomes 
%in the NCBI core tree is less relevant, biologically speaking, than the one obtained
%by using DOGMA naming process (see Section~\ref{sec:discuss}). 
%
%%\begin{sidewaystable}
%\begin{table}
%\centering
%    \begin{tabular}{llllllllll}
%    \hline
%    Method         & \multicolumn{2}{l}{Connected Components} & \multicolumn{6}{l}{ICM-Genes' names} & ICM-Quality test \\ \hline
%    Annotation     & NCBI                 & DOGMA & \multicolumn{3}{l}{NCBI} & \multicolumn{3}{l}{DOGMA} & NCBI and DOGMA   \\
%    Nb. of genomes & 99                   & 99    & 99*              & 97  & 96  & 99    & 97  & 96  & 99               \\
%    Core genome    & 5                    & 3     & 9                & 0   & 28  & 2     & 10  & 28  & 5                \\
%    Pan genome     & 761                  & 445   & 766              & 764 & 737 & 297   & 297 & 297 & 245              \\ \hline
%    \end{tabular}
%\end{table}
%
%% Please remember to add \use{multirow} to your document preamble in order to suppor multirow cells
%\begin{table}[h]
%\begin{tabular}{ccccl}
%\hline
%Nb. of       & Methods                   & Type of & Size of & \multicolumn{1}{c}{Names of core genes}                                                                                                                                                              \\ 
% genomes&&annotation&core genome&\\ \hline
%\multirow{3}{*}{97}  & \multirow{2}{*}{Method 2} & NCBI               & 0                   & -                                                                                                                                                                                                    \\
%\multicolumn{1}{l}{} & \multicolumn{1}{l}{}      & DOGMA              & 10                  & ATPI, PSAA, PSAB, PSBA,  \\
%&&&&PSBE, PSBF, PSBL, RPL2,\\
%&&&& TRNC-GCA, TRNH-GUG \\
%\multicolumn{1}{l}{} & Method 3                  & Both    & 5                   & ATPI, ATPA, ATPH, PSBJ, PSBE                                                                                                                                                                         \\
%\multirow{3}{*}{96}  & \multirow{2}{*}{Method 2} & NCBI               & 28                  & ATPA, ATPB, ATPE, ATPH,\\
%&&&& ATPI, PETG, PSAA, PSAB,\\
%&&&& PSAC, PSBA, PSBD, PSBE,\\
%&&&& PSBF, PSBH, PSBJ, PSBK,\\
%&&&& PSBN, RBCL, RPL14, RPL16,\\
%&&&& RPL20, RPL36, RPS18, RPS3,\\
%&&&& RPS4, RPS7, RPS8, RPS11                         \\
%\multicolumn{1}{l}{} &  & DOGMA & 28                  & ATPA, ATPB, ATPI, ATPH, PETB, PETG, PSAA, PSAB, PSAC, PSBA, PSBD, PSBE, PSBF, PSBC, PSBJ, PSBI, PSBL, PSBT, RBCL, RPL2, RRN16, TRND-GUC, TRNFM-CAU, TRNH-GUG, TRNI-GAU, TRNN-GUU, TRNQ-UUG, TRNC-GCA \\
%\multicolumn{1}{l}{} & \multicolumn{1}{l}{Method 3}      & Both     & 5                   & ATPI, ATPA, ATPH, PSBJ, PSBE                                                                                                                                                                         \\ \hline
%\end{tabular}
%\end{table}
%%\end{sidewaystable}



\subsection{Biological evaluation}\label{sec:discuss}
It is well known that the first plants' endosymbiosis ended in a great diversification of 
lineages comprising \textit{Red Algae}, \textit{Green Algae}, and \textit{Land Plants} (terrestrial).
Several second endosymbioses occurred then: two involving a \textit{Red Algae} 
and other heterotrophic eucaryotes and giving birth to both \textit{Brown Algae} 
and \textit{Dinoflagellates} lineages; another involving a \textit{Green Algae} and 
a heterotrophic eucaryote and giving birth to \textit{Euglens}~\cite{mcfadden2001primary}.

The interesting point with the produced core trees (especially the one 
obtained with DOGMA, see \url{http://members.femto-st.fr/christophe-guyeux/en/chloroplasts}) is 
that organisms resulting from the first endosymbiosis are distributed in 
each of the lineages found in the chloroplast genome structure 
evolution. More precisely, all \textit{Red Algae} chloroplasts are grouped together in one lineage, while
\textit{Green Algae} and \textit{Land Plants} chloroplasts are all in a second lineage. 
Furthermore organisms resulting from the secondary endosymbioses are well localized in 
the tree: both the chloroplasts of \textit{Brown Algae} and \textit{Dinoflagellates} 
representatives are found exclusively in the lineage also comprising the 
\textit{Red Algae} chloroplasts from which they evolved, while the \textit{Euglens} 
chloroplasts are related to the \textit{Green Algae} chloroplasts from which they 
evolved. 
This makes sense in terms of biology, history of lineages, and 
theories of chloroplasts origins (and so photosynthetic ability)  in 
different Eucaryotic lineages~\cite{mcfadden2001primary}.

Interestingly, the sole organisms under consideration that possess a 
chloroplast (and so a chloroplastic genome) but that have lost the 
photosynthetic ability (being parasitic plants) are found at the basis of 
the tree, and not together with their phylogenetically related species. 
This means that functional chloroplast genes are evolutionary constrained 
when used in photosynthetic process, but loose rapidly their efficiency 
when not used, as recently observed for a species of Angiosperms\cite{li2013complete}. 
These species are \textit{Cuscuta-grovonii}, an Angiosperm (flowering plant) 
at the base of the DOGMA Angiosperm-Conifers branch, and 
\textit{Epipactis-virginiana}, also an Angiosperm, at the complete basis of this tree.

Another interesting result is that \textit{Land Plants} that 
represent a single sublineage originating from the large and diverse 
lineage of \textit{Green Algae} in Eucaryotes history are present in two different 
branches of the DOGMA tree, both associated with \textit{Green Algae}: one branch 
comprising the basal grade of \textit{Land Plants} (mosses and ferns) and the second one
containing the most internal lineages of \textit{Land Plants} (Conifers and flowering plants). 
But independently of their split in two distinct branches of the DOGMA 
tree, the \textit{Land Plants} always show a higher number of functional genes in 
their chloroplasts than the \textit{Green Algae} from which they emerged, probably meaning that the
terrestrial way of life necessitates more functional genes for an 
optimal photosynthesis than the marine one. However, a more detailed 
analysis of selected genes is necessary to better understand the reasons why
such a distribution has been obtained.
Remark finally that all these biologically interesting results are apparent
only in the core tree based on DOGMA, while they are not so obvious in the NCBI one. 


%\begin{figure}
%\centering
%\includegraphics[scale=0.37]{core}
%\caption{Core}
%\end{figure}
%
%
%\begin{figure}
%\centering
%\includegraphics[scale=0.37]{pan}
%\caption{Pan}
%\end{figure}
