+ extended documentation
[qpalma.git] / doc / qpalma-manual.tex
index 78f011e..89c6e32 100644 (file)
@@ -7,6 +7,7 @@
 \newcommand{\QPA}{{\sl QPALMA alignment algorithm }}
 \newcommand{\QPH}{{\sl QPALMA approximation }}
 \newcommand{\QPP}{{\sl QPALMA pipeline }}
+\newcommand{\qparam}[1]{{\bf #1}}
 
 \title{QPalma Documentation}
 \author{Fabio De Bona}
 \section{Intro}
 
 \QP is an alignment tool targeted to align spliced reads produced by ``Next
-Generation'' sequencing platforms such as \emph{Illumina Genome Analyzer} or \emph{454}.
-The basic idea is to use an extended Smith-Waterman algorithm for local
-alignments that uses the base quality information of the reads directly in the
-alignment step. Optimal alignment parameters i.e. scoring matrices are inferred
-using a machine learning technique similar to \emph{Support Vector Machines}.
-For further details on \QP itself consult the paper \cite{DeBona08}. For
-details about the learning method see \cite{Tsochantaridis04}.
+Generation'' sequencing platforms such as \emph{Illumina Genome Analyzer} or
+\emph{454}.  The basic idea is to use an extended Smith-Waterman algorithm for
+local alignments that uses the base quality information of the reads directly
+in the alignment step. Optimal alignment parameters i.e. scoring matrices are
+inferred using a machine learning technique similar to \emph{Support Vector
+Machines}.  For further details on \QP itself consult the paper
+\cite{DeBona08}. For details about the learning method see
+\cite{Tsochantaridis04}.
 
 %
 %
 %
 \section{Installation}
 
-The following installation notes assume that you are working on a \emph{Linux}/*NIX
-environment. \emph{Windows} or \emph{MacOS} versions do not exist and are not planned. You
-should have a working \emph{DRMAA} (http://www.drmaa.org/) installation to
-submit jobs to a cluster. \QP is written in C++ and Python and tested on the
-\emph{gcc} compiler suite and python2.5.
+The following installation notes assume that you are working in a
+\emph{Linux}/*NIX environment. \emph{Windows} or \emph{Mac OS} versions do not
+exist and are not planned. You should have a working \emph{DRMAA}
+(http://www.drmaa.org/) installation to submit jobs to a cluster. \QP is
+written in C++ and Python and tested with the \emph{gcc} compiler suite and
+python2.5.
 
 \subsection{Dependencies}
 
-\QP was designed to be as self-contained as possible. However it still has some dependencies.
-In order to install \QP completely you will need:
+\QP was designed to be as self-contained as possible. However it still has some
+dependencies.  In order to install \QP completely you will need:
 \begin{itemize}
 \item $SWIG$, the simple wrapper interface generator,
 \item[$\rightarrow$] http://www.swig.org
@@ -62,7 +65,7 @@ For training \QP you need one of the following optimization toolkits:
 
 \begin{enumerate}
 \item Install the Pythongrid and the Genefinding tool packages
-\item Update your PYTHONPATH variable to poin to the above packages
+\item Update your PYTHONPATH variable to point to the above packages
 \item Unpack the QPalma tarball via
 \item[$\rightarrow$] tar -xzvf QPalma-1.0.tar.gz
 \item Enter the QPalma-1.0 directory and type:
@@ -70,84 +73,163 @@ For training \QP you need one of the following optimization toolkits:
 \end{enumerate}
 \noindent
 In order to check your installation you can run the script
-test\_qpalma\_installation.py which can be found in the directory tests/. This
-script either reports a successful installation or generates an error log file.
-You can send this error log file to qpalma@tuebingen.mpg.de.
-\\ \noindent
+test\_qpalma\_installation.py which can be found in the directory tests/ (Enter
+the directory first as the script works with relative paths). This script
+either reports a successful installation or generates an error log file.  You
+can send this error log file to qpalma@tuebingen.mpg.de.
+\\ \noindent 
 In order to make a full test run with sample data you can run the script
-test\_complete\_pipeline.py. This work on a small artificial dataset performs
-some checks.
+test\_complete\_pipeline.py. this scrips executes the full pipeline with data
+from a small artificial data set.
 
 %
 %
 %
 \section{Working with \QP}
 
-I assume now that you have a successful \QP installation. When working with \QP
-you usually only deal with two commands:
+We assume now that you have a successful \QP installation. When working with \QP
+you usually need two commands:
 
 \begin{itemize}
 \item python qpalma\_pipeline.py train example.conf
 \item python qpalma\_pipeline.py predict example.conf
 \end{itemize}
 \noindent
-\QP has two modes \emph{predict} and \emph{train} all settings are supplied in
+\QP has two modes \emph{predict} and \emph{train}. All settings are supplied in
 a configuration file here example.conf. \\ \noindent
 
+Basically \QP assumes that you have the following data:
+\begin{itemize}
+\item The reads you want to align together with their seed positions,
+\item genomic sequences,
+\item splice site scores predicted for the genomic sequences. 
+\end{itemize}
+
 A typical run consists of 
 \begin{enumerate}
+\item Find the seeds for your reads using another method (NOT VIA \QP). For example vmatch.
 \item Set your parameters (read size, number of mismatches, etc.) in the
 configuration files.
+\item Train a parameter vector once for your organism.
+\item Predict read alignments using the trained parameters.
 \end{enumerate}
-
-Basically \QP assumes that you have the following data:
-\begin{itemize}
-\item The reads you want to align,
-\item parts/full genomic sequences of an organism,
-\item splice site scores predicted for the genomic sequences.
-\end{itemize}
-
-\QP has one central configuration file: 
-
-Suppose you have a
-
-The project results directory (\emph{result\_dir}) contains then the subdirectories
-\begin{itemize}
-\item \emph{mapping} with subdirs main and spliced
-\item \emph{alignment} with subdirs for the different parameters and \emph{heuristic}
-\item \emph{remapping}
-\end{itemize}
+\noindent
+Note: To obtain splice site scores we use the predictions of another tool of
+our group \cite{SonnenburgSchweikertPhilipsBehrRaetsch07}. However this tool is
+not available yet but you can use any splice site prediction tool you prefer as
+long as you stick to the data format described below.
+\\ \\ \noindent
+\QP uses one central configuration file. The parameters you can set in this file are
+described below.
 
 \subsection{The configuration file}
 
-Via the variable ``result\_dir'' you can specify where all of QPalma's data should reside.
-This directory contains the following subdirectories:
+In order to run \QP successfully you will need to create a configuration file.
+All valid parameters for \QP are summarized below. You can also look at the
+example\_configuration.conf file which is included in the distribution.
+\\ \noindent
+The parameters do not have to be in a particular order. In order to simplify
+explanations we have grouped them according to their particular semantics.
+\\ \noindent
+Via the variable ``result\_dir'' you can specify where all of QPalma's data
+should reside. During initialization of \QP the following sub directories of
+result\_dir will be automatically created:
 \begin{itemize}
 \item preprocessing
 \item approximation
+\item dataset
 \item prediction
+\item alignment
 \item postprocessing, and 
-\item training
+\item training.
+\end{itemize}
+\noindent
+Each of these directories will hold all data created in a particular step of the
+\QP pipeline.  The final alignments can be found in the alignment directory.
+\\ \noindent
+The first group consists of general settings for \QP:
+\begin{itemize}
+\item \qparam{perform\_checks}- Enables some checks and debugging output.
+\item \qparam{platform} - IGA or $454$ for Illumina Genome Analyzer or Roche's $454$.
+\item \qparam{result\_dir} - This is the toplevel result directory.
+\item \qparam{spliced\_reads\_fn} - A file consisting of putative spliced reads (obtained for example via vmatch)
+\item \qparam{unspliced\_reads\_fn} - A file consisting of putative unspliced reads (obtained for example via vmatch)
+\item \qparam{num\_splits} - number of computing nodes
+\item \qparam{prediction\_param\_fn} - For prediction needed. This is the location of the trained parameter file.
+\end{itemize}
+\noindent
+The second group includes parameters needed for accessing the sequence data and
+the splice site predictions:
+\begin{itemize}
+\item \qparam{genome\_dir} - The location of the genomic sequence files.
+\item \qparam{acceptor\_scores\_loc} - The location of the acceptor scores files.
+\item \qparam{donor\_scores\_loc} - The location of the acceptor scores files.
+\item \qparam{genome\_file\_fmt} - A format string describing how valid file names are generated. See description below.
+\item \qparam{splice\_score\_file\_fmt} - A format string describing how valid file names for the splice site scores are generated. 
+\item \qparam{allowed\_fragments} - A list of the form ``[1,2,4]'' describing the valid file name numbers. See description below.
+\item \qparam{half\_window\_size} - Given an alignment seed position for a
+given read we cut out the area [1500-seed\_pos,seed\_pos+1500].
+\item \qparam{output\_format} - The output format can be either blat, ShoRe or
+mGene.
+\item \qparam{prb\_offset} - We expect the quality values to be saved as ascii
+strings so the quality is calulated via ord(qchar)-prb\_offset ($ord(\cdot)$
+returns the numeric ascii value). For example an 'h' would correspond to
+quality $40$.
+\end{itemize}
+\noindent
+The genomic sequence and the splice site scores file are accessed using the
+format strings given above. This works as follows: Suppose we have two
+chromosomes 1 \& 4 we want to align to. 
+The sequences are in flat files:
+\begin{center}
+/home/fabio/genomic\_sequence/chromosome\_1.flat \\ \noindent
+/home/fabio/genomic\_sequence/chromosome\_4.flat
+\end{center}
+\noindent
+Then we set genome\_dir to \emph{/home/fabio/genomic\_sequence},
+genome\_file\_fmt to ``chromosome\_\%d.flat'' and allowed\_fragments to [1,4].
+\\ \noindent
+Parameters needed for training are:
+\begin{itemize}
+\item C - this is a parameter trading off between loss term and regularization (similar to C in SVM training).
+\item enable\_quality\_scores - You can enable or disable the use of quality
+scores via settings this parameter to True or False
+\item enable\_splice\_scores - You can enable or disable the use of quality
+scores via settings this parameter to True or False
+\item enable\_intron\_length - You can enable or disable the use of quality
+scores via settings this parameter to True or False
+\item optimizer - Either one of CVXOPT, MOSEK or CPLEX.
+\item numConstraintsPerRound - How many constraints per optimizer call should be generated (if unsure set to $50$).
+\end{itemize}
+\noindent
+For training and prediction purposes you can set the number of support points
+for the piecewise linear functions of the scoring matrix. This effectively
+changes the total number of parameters of the model. That means that you can
+only predict with a parameter vector which was trained with the same settings.
+(We refer to piecewise linear functions as \emph{plifs}.)
+\begin{itemize}
+\item numAccSuppPoints - The number of support points for the plif scoring the acceptor scores.
+\item numDonSuppPoints - The number of support points for the plif scoring the acceptor scores.
+\item numLengthSuppPoints - The number of support points for the plif scoring the acceptor scores.
+\item min\_intron\_len,max\_intron\_len - Set this to the range of minimum and maximum intron lengths.
+\item min\_qual and max\_qual - Set this to the range of possible quality values. (Illumina GA usually [-5,40]).
+\item min\_svm\_score and max\_svm\_score - As we work with normalized (in the
+range [0.0,1.0]) splice site scores this is usually $0.0$ resp. $1.0$.
+\end{itemize}
+\noindent
+The following last group of parameters includes ``low-level'' parameters. Just
+keep the default values of these parameters. Possible extensions of \QP may use
+them differently.
+\begin{itemize}
+\item remove\_duplicate\_scores
+\item print\_matrix
+\item matchmatrixCols, matchmatrixRows
+\item numQualPlifs
+\item numQualSuppPoints
+\item totalQualSuppPoints
+\item anzpath
+\item iter\_steps
 \end{itemize}
-
-%
-%
-%
-\section{Pipeline}
-
-The full pipline consists of $n$ steps:
-
-\begin{enumerate}
-\item Find alignment seeds using a fast suffix array method (vmatch) for
-all given reads. This may take several rounds for subsets of the reads.
-\item Preprocess the reads and their seeds. Convert them to a qpalma format with some sanity checks.
-\item Use the \QPH to identify those reads that have a full seed but might be
-spliced anyways.
-\item Once we identified all potentially spliced reads we use \QPA to align
-those to their seed regions.
-\item One can choose between several post-processing steps in order to refine
-the quality of the alignments via filtering.
-\end{enumerate}
 
 %
 %
@@ -159,8 +241,8 @@ by the users in order to make \QP work.
 
 \subsection{Format of the configuration file}
 
-The configuration file includes are settings \QP needs to perform an analysis.
-This includes paths to file where the raw data exists as well as settings which
+The configuration file includes all settings \QP needs to perform an analysis.
+This includes paths to files where the raw data exists as well as settings which
 sequencing platform is being used,the number of cluster nodes to employ etc. .
 
 Its values are in the form 
@@ -169,37 +251,45 @@ key = value
 \end{center}
 and ``\#'' for lines containing comments.
 
+
 \subsection{Read format and internal representation}
 
-The format of the file containing the mapped short reads is as follows.  Each
-line corresponds to one short read. Each line has six tab-separated entries,
-namely:
+The read input files for \QP contain the read sequences with their quality as
+well as some information from the first mapping / seed region finding. The
+format of the file containing the mapped short reads is as follows.  Each line
+corresponds to one short read. Each line has six tab-separated entries, namely:
 
 \begin{enumerate}
 \item unique read id
 \item chromosome/contig id
-\item position of match in chromosome/contig
+\item position of match in chromosome/contig (0-based, relative to positive strand)
 \item strand 
 \item read sequence (in strand specific direction)
 \item read quality (in strand specific direction)
 \end{enumerate}
 
 Strand specific direction means that \QP assumes that the reads are already in
-their true orientation and the qualities as well. Internally there is no
-reverse complementing taking place.
+their true orientation and the qualities as well.
 
 \subsection{Splice Scores}
 
-The splice site scores where generated by the software... . If you would like
+As mentioned before the splice site scores where generated using a tool
+described in \cite{SonnenburgSchweikertPhilipsBehrRaetsch07}. If you would like
 to use your own splice site predictions you can create files according to the
-format \QP uses.  This splice site scores format is described. For each
-canonical acceptor ($AG$) and donor site ($GT$/$GC$) \QP expects a score. For every
-chromosome or contig we have a four files.  For each strand we have a binary
-file containing the positions and a binary file containing the scores. The
-positions are stored as unsigned values and the scores as floats.  The
-positions are 1-based and the assignment of positions and their scores is as
-follows: The acceptor score positions are the positions right after the $AG$ and the
-donor score positions are the positions right on the $G$ of the $GT$. For example:
+format \QP uses.  This splice site scores format is described below:
+\\ \noindent
+For each canonical acceptor ($AG$) and donor site ($GT$/$GC$) \QP expects a
+score. The data is organized in files for each signal (acc/don) for each strand
+(+/-).  The information on positions of canonical splice sites and the
+corresponding scores lies in separate files.  Every chromosome or contig leads
+then to $8$ files (acc/don, +/- and pos/score).
+The position and score files are raw binary files containing the orderd positions
+and the scores. The positions are stored as unsigned values and the scores as
+floats. Note that you have to be careful when working in an inhomogeneous
+cluster environment (endianness, data type size ). The positions are 1-based
+and the assignment of positions and their scores is as follows: The acceptor
+score positions are the positions right after the $AG$ and the donor score
+positions are the positions right on the $G$ of the $GT$.  For example:
 \begin{center}
 \begin{tabular}{ccccccccccc}
 ... & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & ... \\ 
@@ -207,8 +297,9 @@ donor score positions are the positions right on the $G$ of the $GT$. For exampl
 ... &   & 0.2&  &   &   &   &   &    & 0.3 & ... 
 \end{tabular}
 \end{center}
-We supply a script  for conversion of ascii to binary files. You can use this
-script as a template to make your own scoring information files.
+We supply a script ``spliceScoresConverter.py'' for conversion of ascii to
+binary files. You can use this script as a template to make your own scoring
+information files.
 
 \section{Remarks}
 
@@ -234,6 +325,11 @@ The official \QP project email address is:
    \newblock Support Vector Machine Learning for Interdependent and Sturcutured Output Spaces
    \newblock {\em Proceedings of the 16th International Conference on Machine Learning}, 2004
 
+\bibitem[3]{SonnenburgSchweikertPhilipsBehrRaetsch07}
+   S{\"o}ren~Sonnenburg~and~Gabriele~Schweikert~and~Petra~Philips~and~Jonas~Behr~and~Gunnar~R{\"a}tsch
+   \newblock Accurate splice site prediction using support vector machines
+   \newblock {\em BMC Bioinformatics 2007, 8(Suppl 10):S7}, December 2007
+
 \end{thebibliography}
 %
 %