BA/latex/tex/kapitel/k4_algorithms.tex

%SUMMARY
%- ABSTRACT
%- INTRODUCTION
%# BASICS
%- \acs{DNA} STRUCTURE
%- DATA TYPES
% - BAM/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

\chapter{Compression aproaches}
The process of compressing data serves the goal to generate an output that is smaller than its input data. In many cases, like in gene compressing, the compression is idealy lossless. This means it is possible for every compressed data, to receive the full information that were available in the origin data, by decompressing it. Lossy compression on the other hand, might excludes parts of data in the compression process, in order to increase the compression rate. The excluded parts are typicaly not necessary to transmit the origin information. This works with certain audio and pictures files or network protocols that are used to transmit video/audio streams live.
For \acs{DNA} a lossless compression is needed. To be preceice a lossy compression is not possible, because there is no unnecessary data. Every nucleotide and its position is needed for the sequenced \acs{DNA} to be complete.

\subsection{Huffman encoding}
% list of algos and the tools that use them
The well known Huffman coding, is used in several Tools for genome compression. This subsection should give the reader a general impression how this algorithm works, without going into detail. To use Huffman coding one must first define an alphabet, in our case a four letter alphabet, containing \texttt{A, C, G and T} is sufficient. The basic structure is symbolized as a tree. With that, a few simple rules apply to the structure:
% binary view for alphabet
% length n of sequence to compromize
% greedy algo
\begin{itemize}
  \item every symbol of the alphabet is one leaf
  \item the right branch from every not is marked as a 1, the left one is marked as a 0
  \item every symbol got a weight, the weight is defined by the frequency the symbol occours in the input text
  \item the less weight a node has, the higher the probability is, that this node is read next in the symbol sequence
\end{itemize}
The process of compromising starts with the nodes with the lowest weight and buids up to the hightest. Each step adds nodes to a tree where the most left branch should be the shortest and the most right the longest. The most left branch ends with the symbol with the highest weight, therefore occours the most in the input data.
Following one path results in the binary representation for one symbol. For an alphabet like the one described above, an binary representation could initially look like this \texttt{A -> 00, C -> 01, G -> 10, T -> 11} with a sequence that has this distribution \texttt{A -> 10, C - 8, G -> 3, T -> 2} with a corresponding tree the compromised data would look like this: \texttt{}

% begriffdef. alphabet,
% leafs
% weights
% paths

% (genomic squeeze <- official | inofficial -> GDC, GRS). Further \ac{ANS} or rANS ... TBD.

\section{Probability aproaches}