-The field of Genome annotation pays a lot of attentions where the ability to collect and analysis genomical data can provide strong indicator for the study of life\cite{Eisen2007}. Four of genome annotation centers, (such as, \textit{NCBI\cite{Sayers01012011}, Dogma \cite{RDogma}, cpBase \cite{de2002comparative}, CpGAVAS \cite{liu2012cpgavas}, and CEGMA\cite{parra2007cegma}}), present various types of annotations tools (i.e cost-effective sequencing methods\cite{Bakke2009}) on different annotation levels. Generally, one of three methods of gene finding in annotated genome can be categorized using these centers: \textit{alignment-based, composition based, or combination of both\cite{parra2007cegma}}. The alignment-based method is used when we try to predict a coding gene (i.e. genes that produce proteins) by aligning DNA sequence of gene to the protein of cDNA sequence of homology\cite{parra2007cegma}. This approache also is used in GeneWise\cite{birney2004genewise}. Composition-based mothod (known as \textit{ab initio}) is based on a probabilistic model of gene structure to find genes and/or new genes according to the probability gene value (GeneID\cite{parra2000geneid}). In this section, we will consider a new method of finding core genes from large amount of chloroplast genomes, as a solution of the problem resulting from the method stated in section two. This method is based on extracting gene features. A general overview of the system is illustrated in Figure \ref{Fig1}.\\
-\begin{figure}[H]
+These last years the cost of sequencing genomes has been greatly
+reduced, and thus more and more genomes are sequenced. Therefore
+automatic annotation tools are required to deal with this continuously
+increasing amount of genomical data. Moreover, a reliable and accurate
+genome annotation process is needed in order to provide strong
+indicators for the study of life\cite{Eisen2007}.
+
+Various annotation tools (\emph{i.e.}, cost-effective sequencing
+methods\cite{Bakke2009}) producing genomic annotations at many levels
+of detail have been designed by different annotation centers. Among
+the major annotation centers we can notice NCBI\cite{Sayers01012011},
+Dogma \cite{RDogma}, cpBase \cite{de2002comparative},
+CpGAVAS \cite{liu2012cpgavas}, and
+CEGMA\cite{parra2007cegma}. Usually, previous studies used one out of
+three methods for finding genes in annoted genomes using data from
+these centers: \textit{alignment-based}, \textit{composition based},
+or a combination of both~\cite{parra2007cegma}. The alignment-based
+method is used when trying to predict a coding gene (\emph{i.e.}.
+genes that produce proteins) by aligning a genomic DNA sequence with a
+cDNA sequence coding an homologous protein \cite{parra2007cegma}.
+This approach is also used in GeneWise\cite{birney2004genewise}. The
+alternative method, the composition-based one (also known
+as \textit{ab initio}) is based on a probabilistic model of gene
+structure to find genes according to the gene value probability
+(GeneID \cite{parra2000geneid}). Such annotated genomic data will be
+used to overcome the limitation of the first method described in the
+previous section. In fact, the second method we propose finds core
+genes from large amount of chloroplast genomes through genomic
+features extraction.
+
+Figure~\ref{Fig1} presents an overview of the entire method pipeline.
+More precisely, the second method consists of three
+stages: \textit{Genome annotation}, \textit{Core extraction},
+and \textit{Features Visualization} which highlights the
+relationships. To understand the whole core extraction process, we
+describe briefly each stage below. More details will be given in the
+coming subsections. The method uses as starting point some sequence
+database chosen among the many international databases storing
+nucleotide sequences, like the GenBank at NBCI \cite{Sayers01012011},
+the \textit{EMBL-Bank} \cite{apweiler1985swiss} in Europe
+or \textit{DDBJ} \cite{sugawara2008ddbj} in Japan. Different
+biological tools can analyze and annotate genomes by interacting with
+these databases to align and extract sequences to predict genes. The
+database in our method must be taken from any confident data source
+that stores annotated and/or unannotated chloroplast genomes. We have
+considered the GenBank-NCBI \cite{Sayers01012011} database as sequence
+database: 99~genomes of chloroplasts were retrieved. These genomes
+lie in the eleven type of chloroplast families and Table \ref{Tab2}
+summarizes their distribution in our dataset.
+
+\begin{figure}[h]
\centering
- \includegraphics[width=0.7\textwidth]{generalView}
-\caption{A general overview of the system}\label{Fig1}
+ \includegraphics[width=0.75\textwidth]{generalView}
+\caption{A general overview of the annotation-based approach}\label{Fig1}
\end{figure}
-In Figure 1, we illustrate the general overview of system pipeline: \textit{Database, Genomes annotation, Core extraction,} and \textit{relationships}. We will give a short discussion for each stage of the model in order to understand all core extraction process. This work starts with a gene Bank database; however, many international Banks for nucleotide sequence databases (such as, \textit{GenBank} \cite{Sayers01012011} in USA, \textit{EMBL-Bank} \cite{apweiler1985swiss} in Europe, and \textit{DDBJ} \cite{sugawara2008ddbj} in Japon) where exist to store various genomes and DNA species. Different Biological tools are provided to analyse and annotate genomes by interacting with these databases to align and extract sequences to predict genes. The database in this model must be taken from any confident data source that store annotated and/or unannotated chloroplast genomes. We will consider GenBank-NCBI \cite{Sayers01012011} database to be our nucleotide sequences database. Annotation (as the second stage) is considered to be the first important task for Extract Gene Features. Good annotation tool lead us to extracts good gene feature. In this paper, two annotation techniques from \textit{NCBI, and Dogma} are used to extract \textit{genes features}. Extracting Gene feature (as a third stage) can be anything like (genes names, gene sequences, protein sequence,...etc). Our methodologies in this paper consider gene names, genes counts, and gene sequences for extracting core genes and producing chloroplast evolutionary tree. \\
-In last stage, features visualization represents methods to visualize genomes and/or gene evolution in chloroplast. By using the forms of (tables, phylogenetic trees, graphs,...,etc) to organize and represent genomes relationships can achieve the goal of gene evolution with what the biological expert needs. In addition, compare these forms with another annotation tool forms for large population of chloroplast genomes give us biological perspective to the nature of chloroplasts evolution. \\
-A Local database attached with each pipe stage is used to store all the informations of extraction process. The output from each stage in our system will be an input to the second stage and so on.
-
-\subsection{Genomes Samples}
-In this research, we retrieved genomes of Chloroplasts from NCBI. Ninety nine genome of them were considered to work with. These genomes lies in the eleven type of chloroplast families. The distribution of genomes is illustrated in detail in Table \ref{Tab2}.
-
-\input{population_Table}
-
-\subsection{Genome Annotation Techniques}
-Genome annotation is the second stage in the model pipeline. Many techniques were developed to annotate chloroplast genomes but the problem is that they vary in the number and type of predicting genes (i.e the ability to predict genes and \textit{for example: Transfer RNA (tRNA)} and \textit{Ribosomal RNA (rRNA)} genes). Two annotation techniques from NCBI and Dogma are considered to analyse chloroplast genomes to examine the accuracy of predicted coding genes.
-
-\subsubsection{genome annotation from NCBI}
-The objective from this step is to organize genes, solve gene duplications, and generate sets of genes from each genome. The input to the system is our list of chloroplast genomes, annotated from NCBI. All genomes stored as \textit{.fasta} files which have a collection of protein coding genes\cite{parra2007cegma,RDogma}(gene that produce proteins) with its coding sequences.
-As a preprocessing step to achieve the set of core genes, we need to analyse these genomes (using \textit{BioPython} package\cite{chapman2000biopython}), to extracting all information needed to find the core genes. The process starts by converting each genome from fasta format to GenVision\cite{geneVision} formats from DNASTAR. The outputs from this operation are lists of genes for each genome, their genes names and gene counts. In this stage, we accumulate some Gene duplications for each treated genome. In other words, duplication in gene name can comes from genes fragments, (e.g. gene fragments treated with NCBI), as long as chloroplast DNA sequences. To ensure that all the duplications are removed, each list of genes is translated into a set of genes. NCBI genome annotation produce genes except \textit{Ribosomal rRNA}.
+Annotation, which is the first stage, is an important task for
+extracting gene features. Indeed, to extract good gene feature, a good
+annotation tool is obviously required. To obtain relevant annotated
+genomes, two annotation techniques from NCBI and Dogma are used. The
+extraction of gene feature, the next stage, can be anything like gene
+names, gene sequences, protein sequences, and so on. Our method
+considers gene names, gene counts, and gene sequence for extracting
+core genes and producing chloroplast evolutionary tree. The final
+stage allows to visualize genomes and/or gene evolution in
+chloroplast. Therefore we use representations like tables,
+phylogenetic trees, graphs, etc. to organize and show genomes
+relationships, and thus achieve the goal of representing gene
+evolution. In addition, comparing these representations with ones
+issued from another annotation tool dedicated to large population of
+chloroplast genomes give us biological perspectives to the nature of
+chloroplasts evolution. Notice that a local database linked with each
+pipe stage is used to store all the informations produced during the
+process.
+
+\input{population_Table}
+
+\subsection{Genome annotation techniques}
+
+For the first stage, genome annotation, many techniques have been
+developed to annotate chloroplast genomes. These techniques differ
+from each others in the number and type of predicted genes (for
+example: \textit{Transfer RNA (tRNA)} and \textit{Ribosomal RNA
+(rRNA)} genes). Two annotation techniques from NCBI and Dogma are
+considered to analyze chloroplast genomes.
+
+\subsubsection{Genome annotation from NCBI}
+
+The objective is to generate sets of genes from each genome so that
+genes are organized without any duplication. The input is a list of
+chloroplast genomes annotated from NCBI. More precisely, all genomes
+are stored as \textit{.fasta} files which consists in a collection of
+protein coding genes\cite{parra2007cegma,RDogma} (gene that produce
+proteins) organized in coding sequences. To be able build the set of
+core genes, we need to preprocess these genomes
+using \textit{BioPython} package \cite{chapman2000biopython}. This
+step starts by converting each genome from FASTA file format to
+GenVision \cite{geneVision} format from DNASTAR. Each genome is thus
+converted in a list of genes, with gene names and gene counts. Gene
+name duplications can be accumulated during the treatment of a genome.
+These duplications come from gene fragments (\emph{e.g.} gene
+fragments treated with NCBI) and from chloroplast DNA sequences. To
+ensure that all the duplications are removed, each list of gene is
+translated into a set of genes. Note that NCBI genome annotation
+produces genes except \textit{Ribosomal (rRNA)} genes.
\subsubsection{Genome annotation from Dogma}
-Dogma is an annotation tool developed in the university of Texas in 2004. Dogma is an abbreviation of (\textit{Dual Organellar GenoMe Annotator}) for plant chloroplast and animal mitochondrial genomes.
-It has its own database for translating the genome in all six reading frames and query the amino acid sequence database using Blast\cite{altschul1990basic}(i.e Blastx) with various parameters. Further more, identify protein coding genes in the input genome based on sequence similarity of genes in Dogma database. In addition, it can produce the \textit{Transfer RNAs (tRNA)}, and the \textit{Ribosomal RNAs (rRNA)} and verifies their start and end positions rather than NCBI annotation tool. There are no gene duplication with dogma after solving gene fragmentation. \\
-Genome Annotation with dogma can be the key difference of extracting core genes. The step of annotation divided into two tasks: First, It starts to annotate complete chloroplast genome (i.e \textit{Unannotate genome from NCBI} by using Dogma web tool. This process was done manually. The output from dogma is considered to be collection of coding genes file for each genome in the form of GeneVision file format.
-Where the second task is to solve gene fragments. Two methods used to solve genes duplication for extract core genes. First, for the method based on gene name, all the duplications are removed, where each list of genes is translated into a set of genes. Second, for the method of gene quality test, defragment process starts immediately to solve fragments of coding genes for each genome to avoid gene duplication. In each iteration, this process starts by taking one gene from gene list, search for gene duplication, if exists, look on the orientation of the fragment sequence: if it is positive, then appending fragment sequence to gene file. Otherwise, the process applies reverse complement operations on gene sequence and append it to gene file. Additional process applied to check start and stop codon and try to find appropriate start and end codon in case of missing. All genomes after this stage are fully annotated, their genes were de-fragmented, genes lists and counts were identified.\\
-
-\subsection{Core Genes Extraction}
-The goal of this step is to extract maximum core genes from sets of genes. The methodology of finding core genes is as follow: \\
-\subsubsection{Pre-Processing}
-We apply two pre-processing methods for organize and prepare genomes data, one method based on gene name and count, and the second method is based on sequence quality control test.\\
-In the first method, preparing chloroplasts genomes to extract core genes based on gene name and count starts after annotation process because genomes vary in genes counts and types according to the annotation used method. Then we store each genome in the database under genome name with the set of genes names. Genes counts can extracted simply by a specific length command. \textit{Intersection core matrix} will apply then to extract the core genes. The problem with this method is how we can quarantine that the gene predicted in core genes is the same gene in leaf genomes?. To answer this question, if the sequence of any gene in a genome annotated from dogma and NCBI are similar with respect to a threshold, we do not have any problem with this method. Otherwise, we have a problem, because we can not decide which sequence goes to a gene in core genes.
-The second pre-processing method state: we can predict the best annotated genome by merge the annotated genomes from NCBI and dogma based on the quality of genes names and sequences test. To generate all quality genes of each genome. the hypothesis state: Any gene will be in predicted genome if and only if the annotated genes between NCBI and Dogma pass a specific threshold of\textit{quality control test}. To accept the quality test, we applied Needle-man Wunch algorithm to compare two gene sequences with respect to pass a threshold. If the alignment score pass this threshold, then the gene will be in the predicted genome. Otherwise, the gene will be ignored. After predicting all genomes, \textit{Intersection core matrix} will apply on these new genomes to extract core genes. As shown in Algorithm \ref{Alg3:thirdM}.
+Dogma stands for \textit{Dual Organellar GenoMe Annotator}. It is an
+annotation tool developed at University of Texas in 2004 for plant
+chloroplast and animal mitochondrial genomes. This tool has its own
+database for translating a genome in all six reading frames and
+queries the amino acid sequence database using
+BLAST \cite{altschul1990basic} (\emph{i.e.} Blastx) with various
+parameters. Protein coding genes are identified in an input genome
+using sequence similarity of genes in Dogma database. In addition in
+comparison with NCBI annotation tool, Dogma can produce
+both \textit{Transfer RNAs (tRNA)} and \textit{Ribosomal RNAs (rRNA)},
+verify their start and end positions. Another difference is also that
+there is no gene duplication with Dogma after solving gene
+fragmentation. In fact, genome annotation with Dogma can be the key
+difference when extracting core genes.
+
+The Dogma annotation process is divided into two tasks. First, we
+manually annotate chloroplast genomes using Dogma web tool. The output
+of this step is supposed to be a collection of coding genes files for
+each genome, organized in GeneVision file. The second task is to solve
+the gene duplication problem and therefore we have use two
+methods. The first method, based on gene name, translates each genome
+into a set of genes without duplicates. The second method avoid gene
+duplication through a defragment process. In each iteration, this
+process starts by taking a gene from gene list, searches for gene
+duplication, if a duplication is found, it looks on the orientation of
+the fragment sequence. If it is positive it appends directly the
+sequence to gene files. Otherwise reverse complement operations are
+applied on the sequence, which is then also append to gene files.
+Finally, a check for missing start and stop codons is performed. At
+the end of the annotation process, all the genomes are fully
+annotated, their genes are defragmented, and gene counts are
+available.
+
+\subsection{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{Preprocessing}
+
+In order to extract core genomes in a suitable manner, the genomic
+data are preprocessed with two methods: on the one hand a method based
+on gene name and count, and on the other hand a method based on a
+sequence quality control test.
+
+In the first method, we extract a list of genes from each chloroplast
+genome. Then we store this list of genes in the database under genome
+nam and genes counts can be extracted by a specific length command.
+The \textit{Intersection Core Matrix}, described in next subsection,
+is then computed to extract the core genes. The problem with this
+method can be stated as follows: how can we ensure that the gene which
+is predicted in core genes is the same gene in leaf genomes? The
+answer to this problem is that if the sequences of any gene in a
+genome annotated from Dogma and NCBI are similar with respect to a
+given threshold, then we do not have any problem with this
+method. When the sequences are not similar we have a problem, because
+we cannot decide which sequence belongs to a gene in core genes.
+
+The second method is based on the underlying idea: we can predict the
+the best annotated genome by merging the annotated genomes from NCBI
+and Dogma according to a quality test on genes names and sequences. To
+obtain all quality genes of each genome, we consider the following
+hypothesis: any gene will appear in the predicted genome if and only
+if the annotated genes in NCBI and Dogma pass a specific threshold
+of \textit{quality control test}. In fact, the Needle-man Wunch
+algorithm is applied to compare both sequences with respect to a
+threshold. If the alignment score is above the threshold, then the
+gene will be retained in the predicted genome, otherwise the gene is
+ignored. Once the prediction of all genomes is done,
+the \textit{Intersection Core Matrix} is computed on these new genomes
+to extract core genes, as explained in Algorithm \ref{Alg3:thirdM}.
\begin{algorithm}[H]
-\caption{Extract new genome based on Gene Quality test}
+\caption{Extract new genome based on gene quality test}
\label{Alg3:thirdM}
\begin{algorithmic}
\REQUIRE $Gname \leftarrow \text{Genome Name}, Threshold \leftarrow 65$
\end{algorithmic}
\end{algorithm}
-\textbf{geneChk} is a subroutine, it is used to find the best similarity score between two gene sequences after applying operations like \textit{reverse, complement, and reverse complement}. The algorithm of geneChk is illustrated in Algorithm \ref{Alg3:genechk}.
+\textbf{geneChk} is a subroutine used to find the best similarity score between
+two gene sequences after applying operations like \textit{reverse}, {\it complement},
+and {\it reverse complement}. Algorithm~\ref{Alg3:genechk} gives the outline of
+geneChk subroutine.
\begin{algorithm}[H]
-\caption{Find the Maximum similarity score between two sequences}
+\caption{Find the Maximum Similarity Score between two sequences}
\label{Alg3:genechk}
\begin{algorithmic}
-\REQUIRE $gen1,gen2 \leftarrow \text{NCBI gene sequence, Dogma gene sequence}$
+\REQUIRE $g1,g2 \leftarrow \text{NCBI gene sequence, Dogma gene sequence}$
\ENSURE $\text{Maximum similarity score}$
-\STATE $Score1 \leftarrow needle(gen1,gen2)$
-\STATE $Score2 \leftarrow needle(gen1,Reverse(gen2))$
-\STATE $Score3 \leftarrow needle(gen1,Complement(gen2))$
-\STATE $Score4 \leftarrow needle(gen1,Reverse(Complement(gen2)))$
-\IF {$max(Score1, Score2, Score3, Score4)==Score1$}
- \RETURN $Score1$
-\ELSIF {$max(Score1, Score2, Score3, Score4)==Score2$}
- \RETURN $Score2$
-\ELSIF {$max(Score1, Score2, Score3, Score4)==Score3$}
- \RETURN $Score3$
-\ELSIF {$max(Score1, Score2, Score3, Score4)==Score4$}
- \RETURN $Score4$
-\ENDIF
+\STATE $score1 \leftarrow needle(g1,g2)$
+\STATE $score2 \leftarrow needle(g1,Reverse(g2))$
+\STATE $score3 \leftarrow needle(g1,Complement(g2))$
+\STATE $score4 \leftarrow needle(g1,Reverse(Complement(g2)))$
+\RETURN $max(score1,score2,score3,score4)$
\end{algorithmic}
\end{algorithm}
\subsubsection{Intersection Core Matrix (\textit{ICM})}
-The idea behind extracting core genes is to collect iteratively the maximum number of common genes between two genomes. To do so, the system builds an \textit{Intersection core matrix (ICM)}. ICM is a two dimensional symmetric matrix where each row and column represent one genome. Each position in ICM stores the \textit{intersection scores(IS)}. The Intersection Score is the cardinality number of a core genes which comes from intersecting one genome with other ones. Maximum cardinality results to select two genomes with their maximum core. Mathematically speaking, if we have an $n \times n$ matrix where $n=\text{number of genomes in local database}$, then lets consider:\\
-
+To extract core genes, we iteratively collect the maximum number of
+common genes between genomes and 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 one genome with another
+one. 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=\max_{i<j}\vert x_i \cap x_j\vert
+score_{ij}=\vert g_i \cap g_j\vert
\label{Eq1}
-\end{equation}\\
-
-Where $x_i, x_j$ are elements in the matrix. The generation of a new core genes is depending on the cardinality value of intersection scores, we call it \textit{Score}:
-$$\text{New Core} = \begin{cases}
-\text{Ignored} & \text{if $\textit{Score}=0$;} \\
-\text{new Core id} & \text{if $\textit{Score}>0$.}
-\end{cases}$$
-
-if $\textit{Score}=0$ then we have \textit{disjoint relation} (i.e no common genes between two genomes). In this case the system ignores the genome that annul the core genes size. Otherwise, The system will removes these two genomes from ICM and add new core genomes with a \textit{coreID} of them to ICM for the calculation in next iteration. This process will reduce the size of ICM and repeat until all genomes are treated (i.e ICM has no more genomes).
-We observe that ICM is very large because of the amount of data that it stores. This results to be time and memory consuming for calculating the intersection scores. To increase the speed of calculations, it is sufficient to only calculate the upper triangle scores. The time complexity for this process after enhancement is thus $O(\frac{(n-1).n}{2})$. Algorithm \ref{Alg1:ICM} illustrates the construction of the ICM matrix and the extraction of the core genes where \textit{GenomeList}, represents the database where all genomes data are stored. At each iteration, it computes the maximum core genes with its two genomes parents.
+\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 gene 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 ICM. These two genomes are then removed from 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 gene: new IS
+values are computed for it. This process is repeated until no new core
+gene can be obtained.
+
+We can observe that the ICM is very large due to the amount of
+data. As a consequence, the computation of the intersection scores is
+both time and memory consuming. However, since ICM is a symetric
+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 genes, where \textit{GenomeList} represents the database
+storing all genomes data. At each iteration, it computes the maximum
+core genes with its two genomes parents.
+
+% ALGORITHM HAS BEEN REWRITTEN
\begin{algorithm}[H]
\caption{Extract Maximum Intersection Score}
\label{Alg1:ICM}
\begin{algorithmic}
\REQUIRE $L \leftarrow \text{genomes vectors}$
-\ENSURE $B1 \leftarrow Max core vector$
+\ENSURE $B1 \leftarrow Max Core Vector$
\FOR{$i \leftarrow 0:len(L)-1$}
+ \STATE $score \leftarrow 0$
\STATE $core1 \leftarrow set(GenomeList[L[i]])$
- \STATE $score1 \leftarrow 0$
- \STATE $g1,g2 \leftarrow$ " "
+ \STATE $g1 \leftarrow L[i]$
\FOR{$j \leftarrow i+1:len(L)$}
- \STATE $core2 \leftarrow set(GenomeList[L[i]])$
- \IF{$i < j$}
- \STATE $Core \leftarrow core1 \cap core2$
- \IF{$len(Core) > score1$}
- \STATE $g1 \leftarrow L[i]$
- \STATE $g2 \leftarrow L[j]$
- \STATE $Score \leftarrow len(Core)$
- \ELSIF{$len(Core) == 0$}
- \STATE $g1 \leftarrow L[i]$
- \STATE $g2 \leftarrow L[j]$
- \STATE $Score \leftarrow -1$
- \ENDIF
- \ENDIF
+ \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[score1] \leftarrow (g1,g2)$
+ \STATE $B1[score] \leftarrow (g1,g2)$
\ENDFOR
\RETURN $max(B1)$
\end{algorithmic}
\end{algorithm}
-\subsection{Features Visualization}
-The goal here is to visualize the results by building a tree of evolution. All Core genes generated with their genes are very important information in the tree, because they can be viewed as an ancestor information for two genomes or more. Further more, each node represents a genome or core as \textit{(Genes count:Family name, Scientific names, Accession number)}, Edges represent numbers of lost genes from genomes-core or core-core relationship. The number of lost genes here can represent an important factor for evolution, it represents how much lost of genes for the species in same or different families. By the principle of classification, small number of gene lost among species indicate that those species are close to each other and belong to same family, while big genes lost means that we have an evolutionary relationship between species from different families. To see the picture clearly, Phylogenetic tree is an evolutionary tree generated also by the system. Generating this tree is based on the distances among genes sequences. There are many resources to build such tree (for example: PHYML\cite{guindon2005phyml}, RAxML{\cite{stamatakis2008raxml,stamatakis2005raxml}, BioNJ , and TNT\cite{goloboff2008tnt}}. We consider to use RAxML\cite{stamatakis2008raxml,stamatakis2005raxml} because it is fast and accurate for build large trees for large count of genomes sequences. The procedure of constructing phylogenetic tree stated in the following steps:
-
+\subsection{Features visualization}
+
+The goal is to visualize results by building a tree of evolution. All
+core genes generated represent important information in the tree,
+because they provide information about the ancestors of two or more
+genomes. Each node in the tree represents one chloroplast genome or
+one predicted core called \textit{(Genes count:Family name\_Scientific
+names\_Accession number)}, while an edge is labeled with the number of
+lost genes from a leaf genome or an intermediate core gene. Such
+numbers are very interesting because they give an information about
+the evolution: how many genes were lost between two species whether
+they belong to the same familie or not. By the principle of
+classification, a small number of genes lost among species indicates
+that those species are close to each other and belong to same family,
+while a large lost means that we have an evolutionary relationship
+between species from different families. To depict the links between
+species clearly, we built a phylogenetic tree showing the
+relationships based on the distances among genes sequences. Many tools
+are available to obtain a such tree, for example:
+PHYML\cite{guindon2005phyml},
+RAxML{\cite{stamatakis2008raxml,stamatakis2005raxml}, BioNJ, and
+TNT\cite{goloboff2008tnt}}. In this work, we chose to use
+RAxML\cite{stamatakis2008raxml,stamatakis2005raxml} because it is
+fast, accurate, and can build large trees when dealing with a large
+number of genomic sequences.
+
+The procedure used to built a phylogenetic tree is as follows:
\begin{enumerate}
-\item Extract gene sequence for all gene in all core genes, store it in database.
-\item Use multiple alignment tool such as (****to be write after see christophe****) to align these sequences with each others.
-\item aligned genomes sequences then submitted to RAxML program to compute the distances and draw phylogenetic tree.
+\item For each gene in a core gene, extract its sequence and store it in the database.
+\item Use multiple alignment tools such as (****to be write after see christophe****)
+to align these sequences with each others.
+\item Submit the resulting aligned sequences to RAxML program to compute the distances and finally draw the phylogenetic tree.
\end{enumerate}
\begin{figure}[H]
- \centering
- \includegraphics[width=0.7\textwidth]{Whole_system}
- \caption{Total overview of the system pipeline}\label{wholesystem}
+ \centering \includegraphics[width=0.75\textwidth]{Whole_system}
+ \caption{Overview of the pipeline}\label{wholesystem}
\end{figure}
\section{Implementation}
The pipeline of extracting core genes can summarize in the following steps according to pre-processing method used:\\
\begin{enumerate}
-\item We downloads already annotated chloroplast genomes in the form of fasta coding genes (i.e \textit{exons}).
+\item We downloads already annotated chloroplast genomes in the form of fasta coding genes (\emph{i.e.} \textit{exons}).
\item Extract genes names and apply to solve gene duplication using first method.
\item Convert fasta file format to geneVision file format to generate ICM.
\item Calculate ICM matrix to find maximum core \textit{Score}. New core genes for two genomes will generate and a specific \textit{CoreId} will assign to it. This process continue until no elements remain in the matrix.
extracting core genes based on genes names and counts summarized in the following steps:\\
\begin{enumerate}
\item We apply the genome annotation manually using Dogma annotation tool.
-\item Analysing genomes to store lists of code genes names (i.e \textit{exons}). solve gene fragments is done by using first method in solve gene fragments. The output from annotation process with dogma is genomes files in GenVision file format. Sets of genes were stored in the database.
+\item Analysing genomes to store lists of code genes names (\textit{i.e. exons}). solve gene fragments is done by using first method in solve gene fragments. The output from annotation process with dogma is genomes files in GenVision file format. Sets of genes were stored in the database.
\item Generate ICM matrix to calculate maximum core genes.
\item Draw the evolutionary tree by extracted all genes sequences from each core. Then applying multiple alignment process on the sequences to calculate the distance among cores to draw a phylogenetic tree.
