%SUMMARY
%- ABSTRACT
%- INTRODUCTION
%# BASICS
%- \acs{DNA} STRUCTURE
%- DATA TYPES
% - BAM/\acs{FASTq}
% - NON STANDARD
%- COMPRESSION APPROACHES
% - SAVING DIFFERENCES WITH GIVEN BASE \acs{DNA}
% - HUFFMAN ENCODING
% - PROBABILITY APPROACHES (WITH BASE?)
%
%# COMPARING TOOLS
%- 
%# POSSIBLE IMPROVEMENT
%- \acs{DNA}S STOCHASTICAL ATTRIBUTES 
%- IMPACT ON COMPRESSION

% bigger picture - structure chapters like this:
% what is it/how does it work
% where are limits (e.g. BAM)
% what is our focus (and maybe 'why')

\section{File Formats used to Store DNA}
\label{chap:file formats}
As described in previous chapters \ac{DNA} can be represented by a string with the buildingblocks A,T,G and C. Using a common file format for saving text would be impractical because the amount of characters or symbols in the used alphabet defines how many bits are used to store each single symbol.\\
The \ac{ASCII} \cite{iso-ascii} table is a character set registered in 1975, and to this day it is still in use to encode texts digitally. For the purpose of communication larger character sets replaced \acs{ASCII}. It is still used in situations where storage is short.\\
% grund dass ASCII abgelöst wurde -> zu wenig darstellungsmöglichkeiten. Pro heute -> weniger overhead pro character
The buildingblocks of \acs{DNA} require a minimum of four letters, so at least two bits are needed. Storing a single \textit{A} with \acs{ASCII} encoding, requires 8 bit (\,excluding magic bytes and the bytes used to mark the \ac{EOF})\,. Since there are at least $2^8$ or 128 displayable symbols with \acs{ASCII} encoding, this leaves a great overhead of unused combinations.\\
% cout out examples. Might be needed later or elsewhere
% \texttt{00 -> A, 01 -> T, 10 -> G, 11 -> C}. 
In most tools, more than four symbols are used. This is due to the complexity in sequencing \acs{DNA}. It is not 100\% preceice, so additional symbols are used to mark nucleotides that could not or could only partly get determined. Furthermore a so called quality score is used to indicate the certainty of correct sequencing for each nucleotide \cite{survey, Cock_2009}.\\
More common everyday-usage text encodings like unicode require 16 bits per letter. So, settling with \acs{ASCII} has improvement capabilities and is, on the other side, more efficient than using bulkier alternatives like unicode.\\

% differences between information that is store
Formats for storing uncompressed genomic data, can be sorted into several categories. Three noticeable ones would be \cite{survey}:
\begin{itemize}
	\item Sequence variation
	\item Aligned data
	\item Sequenced reads
\end{itemize}
The categories are listed in descending order, based on their complexity, considering their usecase and data structure. Starting with sequence variation, called haplotype which describes formats storing graph based structures that focus on analyzing variations in different genomes \cite{haplo, sam12}. 
Sequenced reads focus on storing continuous protein chains from a sequenced genome \cite{survey}.
Aligned data is somewhat simliar to sequenced reads with the difference that instead of a whole chain of genomes, overlapping subsequences are stored. This could be described as a rawer form of sequenced reads. This way aligned data stores additional information on how certain a specific part of a genome is read correctly \cite{survey, sam12}.
The focus of this work is the compression of sequenced data but not the likelihood of how accurate the data might be. Therefore, only formats that are able to store sequenced reads will be worked with. Note that some algigned data formats are also able to store aligned reads, since latter is just a less informative representation of the first \cite{survey, sam12}.\\

% ausschluss criteria
Several people and groups have developed different file formats to store genomes. Unfortunately, the only standard for storing genomic data is fairly new \cite{isompeg, mpeg}. Therefore, formats and tools implementing this standard are mostly still in development. In order to not go beyond scope, this work will focus only on file formats that fulfill the following criteria:\\
\begin{itemize}
  \item{The format has reputation. This can be indicated through:}
	\begin{itemize}
		\item{A scientific paper, that proved its superiority to other relevant tools.}
		\item{A broad usage of the format determined by its use on ftp servers, which focus on supporting scientific research.}
	\end{itemize}
  \item{The format should not specialize on only one type of \acs{DNA} or target a specific technology.}
  \item{The format stores nucleotide sequences and does not necessarily include \ac{IUPAC} codes besides A, C, G and T \cite{iupac}.}
  \item{The format is open source. Otherwise, optimizations cannot be tested without buying the software and/or requesting permission to disassemble and reverse engineer the software or parts of it.}
\end{itemize}

Information on available formats was gathered through various Internet platforms \cite{ensembl, ucsc, ga4gh} and scientific papers \cite{survey, sam12, Cock_2009}. 
Some common file formats are:\\

\begin{itemize}
% which is relevant? 
  \item{\ac{FASTA}/Multi-\acs{FASTA}}
  \item{\ac{FASTq} \cite{Cock_2009}} 
  \item{\ac{SAM}/\ac{BAM}} \cite{sam12, bam}
  \item{\ac{CRAM}} \cite{sam12, bam}
  %\item{twoBit} \cite{twobit}
\end{itemize}

% groups: sequence data, alignment data, haplotypic
% src: http://help.oncokdm.com/en/articles/1195700-what-is-a-bam-fastq-vcf-and-bed-file
Since methods to store this kind of data are still in development, there are many more file formats. From the selection listed above, \acs{FASTA} and \acs{FASTq} seem to have established the reputation of an unoficial standard for sequenced reads \cite{survey, geco, sam12, vertical, cram-origin}.\\
Considering the first criteria, by searching through anonymously accessible \acs{FTP} servers, only two formats are used commonly: FASTA or its extension \acs{FASTq} and the \acs{BAM} Format \cite{ftp-igsr, ftp-ncbi, ftp-ensembl}.
% todo Explain twobit: The last format, called twoBit is also included, because it is 

\subsection{\acs{FASTA} and \acs{FASTq}}
The rather simple \acs{FASTA} format, is widely used when it comes to storing sequenced reads, without a quality score \cite{sam12, survey}. Since it is an uncompressed format, \acs{FASTA} files are often transmitted compressed with an external tool like gzip \cite{ftp-ensembl, ftp-ncbi}.\\

\begin{figure}[h]
  \centering
  \includegraphics[width=14cm]{k3/fasta-structure.png}
  \caption{Edited example of a \acs{FASTA} file. The original was received from the ensemble server \cite{ftp-ensembl}.}
  \label{k3:fasta-struct}
\end{figure}

The format consists of two repeated sections. The first section consists of one line and stores metadata about the sequenced genome and the file itself. This line, also called header, contains a comment section starting with \texttt{>} followed by a custom text \cite{alok17, Cock_2009}. The comment section is usually used to store information about the sequenced genome and sometimes metadata about the file itself like its size in bytes.\\
The other section contains the sequenced genome whereas each nucleotide is represented by the character \texttt{A, C, G or T}. There are more nucleotide characters that store additional information and some characters for representing amino acids, but in order to not go beyond scope, only \texttt{A, C, G, and T} will be paid attention to \cite{iupac}.\\
The second section can have multiple lines of sequences. A similar format is the Multi-\acs{FASTA} file format, it consists of concatenated \acs{FASTA} files.\cite{survey}.\\
% fastq
In addition to its predecessor, \acs{FASTq} files contain a quality score. The file content consists of four sections, where no section is stored in more than one line. All four lines contain information about one sequence. The exact structure of \acs{FASTq} is formated in this order \cite{Cock_2009}:
\begin{itemize}
	\item Line 1: Sequence identifier aka. Title, starting with an @ and an optional description.
	\item Line 2: The sequence consisting of nucleoids, symbolized by A, T, G and C.
	\item Line 3: A '+' that functions as a separator or delimitier. Optionally followed by the content of line 1.
	\item Line 4: Quality line(s). consisting of letters and special characters in the \acs{ASCII} scope.
\end{itemize}
The quality scores have no fixed format. To name a few, there is the Sanger format, the Solexa format introduced by Solexa Inc., the Illumina and the QUAL format which is generated by the PHRED software \cite{Cock_2009}.\\

\begin{figure}[h]
  \centering
  \includegraphics[width=13cm]{k3/fastq-structure.png}
  \caption{Altered example of a \acs{FASTq} file. The original was received from ncbi server \cite{ftp-ncbi}.}
  \label{k3:fastq-struct}
\end{figure}

In \ref{k3:fasta-struct} the described structure is illustrated. The sequence and the delmitier section were altered, to illustrate the stucture of this format better.
In the header section, \texttt{SRR002906.1} is the sequence identifier; the text that follows is a description. In the delimiter line, the header section without the leading @ could be written again. The last line shows the header for the second sequence.\\

\label{k2:sam}
\subsection{Sequence Alignment Map}
% src https://github.com/samtools/samtools
\acs{SAM} often seen in its compressed, binary representation \acs{BAM} with the fileextension \texttt{.bam}, is part of the SAMtools package, a utility tool for processing SAM/BAM and CRAM files. The SAM/BAM file is a text based format delimited by the whitespace character called tabulation or \textbf{tab} for short \cite{sam12}. It uses 7-bit US-\acs{ASCII}; to be precise charset \acs{ANSI} X3.4-1968 \cite{rfcansi}. The structure is more complex than the one in \acs{FASTq} and described best, accompanied by an example:

\begin{figure}[h]
  \centering
  \includegraphics[width=14cm]{k3/sam-structure.png}
  \caption{\acs{SAM} file structure example \cite{bam}.}
  \label{k2:bam-struct}
\end{figure}

Compared to \acs{FASTA} \acs{SAM} and further compression forms, store more information. As displayed in \ref{k2:bam-struct} this is done by adding, identifier for Reads e.g. \textbf{+r003}, aligning subsequences and writing additional symbols like dots e.g. \textbf{ATAGCT......} in the split alignment +r004 \cite{survey}. A full description of the information stored in \acs{SAM} files would be of little value to this work, therefore further information on is left out but can be found in \cite{sam12} or at \cite{bam}.\\
Samtools provide the feature to convert a \acs{FASTA} file into \acs{SAM} format. Since there is no way to calculate the mentioned additional information from the information stored in \acs{FASTA}, the converted files only store two lines. The first line stores metadata about the file and the second stores the nucleotide sequence in just one line.
