X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chloroplast13.git/blobdiff_plain/cd18f1df3aeca00c0c28a2437b36b590a0066a55..f732f6bb4443a951d307f0faeb33117b78b6e7a5:/annotated.tex diff --git a/annotated.tex b/annotated.tex index 30ad502..8df919c 100644 --- a/annotated.tex +++ b/annotated.tex @@ -1,4 +1,4 @@ -The field of Genome annotation pay a lot of attentions where the ability to collect and analysis genomical data can provide strong indicator for the study of life\cite{Eisen2007}. A lot of genome annotation centers present various types of annotations tools (i.e cost-effective sequencing methods\cite{Bakke2009}) on different annotation levels. Two method of gene finding in annotated genome can be categorized as: 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 used in GeneWise\cite{birney2004genewise} with known splicing signals. 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, this method like 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 previous method where stated in section two. This method is based on extracting gene features. The question now is how can we have good annotation genome? To answer this question, we need to focusing on studying the annotation accuracy\cite{Bakke2009} of the genome. A general overview of the system is illustrated in Figure \ref{Fig1}.\\ +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] \centering @@ -6,79 +6,41 @@ The field of Genome annotation pay a lot of attentions where the ability to coll \caption{A general overview of the system}\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 in the model in order to understand all core extraction process. Good database (as a first stage) will produce good results, however, many international Banks for nucleotide sequence databases like (GenBank in USA, EMBL-Bank in Europe, and DDBJ in Japon) where exists to store various genomes and DNA species. A lot of Biological tool interact with these databases for (Genome Annotation, Gene extraction, alignments, ... , etc). 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 database to be our nucleotide sequences database. Annotation (as the second stage) is consider to be the first important task for Extract Gene Features. Thanks to good annotation tool that lead us to extract good gene features. In this paper, two annotation techniques from \textit{NCBI, and Dogma} will be 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 will consider gene names, gene counts, and gene sequences for extracting core genes and producing chloroplast evolutionary tree. \\ -In last stage, for achieving our goals with what the biological expert needs, we used the form of (tables, phylogenetic trees, graphs,...,etc) to organize and represent genomes relationships and gene evolution. In addition, comparing these forms with the results from another annotation tool like Dogma\cite{RDogma} for large population of chloroplast genomes that give us biological perspective to the nature of chloroplast evolution. \\ -A Local database attached with each pipe stage used to store all information of extraction process. The output from each stage in our system will be an input to the second stage and so on. +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} \citep{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 \citep{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} used to extract \textit{one 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, gene counts, and gene sequences for extracting core genes and producing chloroplast evolutionary tree. \\ + +In last stage, to achieve the goal of gene evolution with what the biological expert needs, we used the form of (tables, phylogenetic trees, graphs,...,etc) to organize and represent genomes relationships. 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 107 genomes of Chloroplasts from NCBI. Ninety nine genomes of them were considered to work with. These genomes lies in the 11 type of chloroplast families, as shown in Table \ref{Tab1}. The distribution of genomes illustrated in detail in Table \ref{Tab2}. - -\begin{table}[H] -\caption{distribution on Chloroplast Families}\label{Tab1} -\centering -\begin{tabular}{c c} -\hline\hline -Family & Genome Counts \\ [0.5ex] -\hline -Brown Algae & 11 \\ -Red Algae & 03 \\ -Green Algae & 17 \\ -Angiosperms & 46 \\ -Brypoytes & 03 \\ -Dinoflagellates & 02 \\ -Euglena & 02 \\ -Fern & 05 \\ -Gymnosperms & 07 \\ -Lycopodiophyta & 02 \\ -Haptophytes & 01 \\ [1ex] -\hline -\end{tabular} -\end{table} +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, as shown in Table \ref{Tab1}. The distribution of genomes is illustrated in detail in Table \ref{Tab2}. \input{population_Table} \subsection{Genome Annotation Techniques} -Genome annotation is considered as the second stage in the model pipeline. Many annotation techniques were developed for 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: Transfere 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. Figure \ref{NCBI_annotation}, illstrate two annotation technique.\\ - -\begin{figure}[H] -\centering -\includegraphics[width=0.7\textwidth]{NCBI_annotation} -\caption{Genome annotation using either NCBI or Dogma}\label{NCBI_annotation} -\end{figure} - -With each annotation model, we provide a quality check class for the flow of chloroplast genomes, as illustrated in figure \ref{NCBI:Annotation}. This class has a direct access to NCBI taxonomy database based on genome accession number to retrieve information for the genome. These information contains \textit{[Scientific name, lineage, Division, taxonomy ID, parentID, and Accession No]}. Examining each genome with this class (i.e based on some parameters), can ignore some genomes from this competition that not match a specific control condition. +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: Transfere 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 genes duplications, and generate sets of genes from each genome. The input to the system is our list of chloroplast genomes, annotated from NCBI\cite{Sayers01012011}. All genomes stored as \textit{.fasta} files include collection of Protein coding genes\cite{parra2007cegma,RDogma}(gene that produce proteins) with its coding sequences. -As a preparation step to achieve the set of core genes, we need to translate these genomes using \textit{BioPython} package\cite{chapman2000biopython}, and extracting all information needed to find the core genes. A process starts by converting each genome in fasta format to GenVision\cite{geneVision} formats from DNASTAR, and this is not an easy job. The output from this operation is a lists of genes stored in a local database for each genome, their genes names and gene counts. In this stage, we will accumulate some Gene duplications with each genome treated. In other words, duplication in gene name can comes from genes fragments as long as chloroplast DNA sequences. We defines \textit{Identical state} to be the state that each gene present only one time in a genome (i.e Gene has no copy) without considering the position or gene orientation. This state can be reached by filtering the database from redundant gene name. To do this, we have two solutions: first, we made an orthography checking. Orthographe checking is used to merge fragments of a gene to form one gene. -Second, we convert the list of genes names for each genome (i.e. after orthography check) in the database to be a set of genes names. Mathematically speaking, if $G=\left[g_1,g_2,g_3,g_1,g_3,g_4\right]$ is a list of genes names, by using the definition of a set in mathematics, we will have $set(G)=\{g_1,g_2,g_3,g_4\}$, and $|G|=4$ where $|G|$ is the cardinality number of the set $G$ which represent the number of genes in the set.\\ -The whole process of extracting core genome based on genes names and counts among genomes is illustrate in Figure \ref{NCBI:Annotation}.\\ - -\begin{figure}[H] - \centering - \includegraphics[width=0.7\textwidth]{NCBI_GeneName} - \caption{NCBI Annotation for Chloroplast genomes} - \label{NCBI:Annotation} -\end{figure} +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 include collection of protein coding genes\cite{parra2007cegma,RDogma}(gene that produce proteins) with its coding sequences. +As a preparation 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 as long as chloroplast DNA sequences. We defines \textit{Identical state} to be the state that each gene present only one time in a genome (i.e Gene has no copy) without considering the position or gene orientation. This state can be reached by filtering the database from redundant gene name. \subsubsection{Genome annotation from Dogma} -Dogma is an annotation tool developed in the university of Texas by \cite{RDogma} in 2004. Dogma is an abbreviation of \textit{Dual Organellar GenoMe Annotator}\cite{RDogma} for plant chloroplast and animal mitochondrial genomes. -It has its own database for translated the genome in all six reading frames and query the amino acid sequence database using Blast\cite{altschul1990basic}(i.e Blastx) with various parameters, and to identify protein coding genes\cite{parra2007cegma,RDogma} in the input genome based on sequence similarity of genes in Dogma database. Further more, it can produce the \textit{Transfer RNAs (tRNA)}\cite{RDogma}, and the \textit{Ribosomal RNAs (rRNA)}\cite{RDogma} and verifying their start and end positions rather than NCBI annotation tool. There are no gene duplication with dogma after solving gene fragmentation. \\ +Dogma \cite{RDogma} 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\cite{parra2007cegma,RDogma} 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 Anntation with dogma can be the key difference of extracting core genes. In figure \ref{dog:Annotation}, The step of annotation divided into two tasks: First, It starts to annotate complete choloroplast genomes (i.e \textit{Unannotated genomes} from NCBI by using Dogma web tool. The whole annotation 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\cite{geneVision} file format.\\ -Where the second task is to solve gene fragments. Defragment process starts immediately after the first task to solve fragments of coding genes for each genome to avoid gene duplication. This process will looks on fragement orientation, if it is negative, then the process apply reverse complement operations on gene sequence. All genomes after this stage are fully annotated, their genes were de-fragmented, genes lists and counts were identified. These information stored in local database.\\ +Where the second task is to solve gene fragments. Defragment process starts immediately after the first task to solve fragments of coding genes for each genome to avoid gene duplication. This process looks for fragment orientation: if it is negative, then the process applis reverse complement operations on gene sequence. All genomes after this stage are fully annotated, their genes were de-fragmented, genes lists and counts were identified.\\ + \begin{figure}[H] \centering \includegraphics[width=0.7\textwidth]{Dogma_GeneName} \caption{Dogma Annotation for Chloroplast genomes}\label{dog:Annotation} \end{figure} -From these two tasks, we can obtain clearly one copy of coding genes. To ensure that genes produced from dogma annotation process is same as the genes in NCBI. We apply in parrallel a quality checking process that align each gene from dogma and NCBI with respect to a specific threshold.\\ - -\subsection{Extract Core Genes} -The goal of this step is trying to extract maximum core genes from sets of genes (\textit{Vectors}) in the local database. The methodology of finding core genes is dividing to three methods: \\ +\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 divided into three methods: \\ -The hypothesis in first method is based on extracting core genes by finding common genes among chloroplast genomes based on extracting gene feature (i.e Gene names, genes counts). Genomes vary in genes counts according to the method of annotation used, so that extracting maximum core genes can be done by constructing Intersection Core Matrix (\textit{ICM}).\\ -While the hypothesis of second method is based on comparing the sequence of reference genes of one annotated genome with other unannotated genomes sequences in Blast database, by using Blastn\cite{Sayers01012011} (nucleotide sequence alignment tool from NCBI). The last method, is based on merge all genes from NCBI and Dogma annotation, then apply a sequence similarity base method (Quality Control test) using Needle-man Wunch algorithm to predict a new genomes. Using predicted genomes to extract core genes using previous methods. Figure \ref{wholesystem}, illustrate the whole system operations. +The first method is based on extracting core genes by finding common genes feature (i.e Gene names, genes counts). Genomes vary in genes counts according to the annotation used method, so that extracting core genes can be done by constructing Intersection Core Matrix (\textit{ICM}).\\ +While the second method is based on comparing the sequence of reference genes of one annotated genome with other unannotated genomes sequences in Blast database, by using Blastn\cite{Sayers01012011} (nucleotide sequence alignment tool from NCBI). The last method, is based on merge all genes from NCBI and Dogma annotation, then apply a sequence similarity base method (Quality Control test) using Needle-man Wunch algorithm to predict a new genomes. Using predicted genomes to extract core genes using previous methods. Figure \ref{wholesystem}, illustrate the whole system operations. \begin{figure}[H] \centering @@ -86,14 +48,14 @@ While the hypothesis of second method is based on comparing the sequence of ref \caption{Total overview of the system pipeline}\label{wholesystem} \end{figure} -In the first method, the idea is to collect from each iteration the maximum number of common genes. To do so, the system build an \textit{Intersection core matrix(ICM)}. ICM here is a two dimensional symmetric matrix (considered as a vector space) where each row and column represent a vector for one genome. Each position in ICM stores the \textit{intersection scores}. Intersection Score(IS) is the cardinality number of a core genes comes from intersecting one vector with other vectors in vector space. Taking maximum cardinality from each row and then take the maximum of them will result to select the maximum cardinality in the vector space. Maximum cardinality results to select two genomes with their maximum core. Mathematically speaking, if we have an $n \times m$ vector space matrix where $n=m=\text{number of vectors in local database}$, then lets consider:\\ +In the first method, the idea is to iterativelly collect the maximum number of common genes. 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 comes from intersecting one ????? with other ??????. 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:\\ \begin{equation} Score=\max_{i0$.}