The genomes of all animals, plants and fungi are organized into chromosomes, which contain a sequence of the four nucleotides A, T, C and G. Chromosomes are further arranged into homologous groups, where two or more chromosomes are almost exact copies of each others. Species whose homologous groups contain pairs of chromosomes, such as humans, are called diploid. Species with more than two chromosomes in a homologous group are called polyploid.
DNA sequencing technologies do not read an entire chromosome from end to end. Instead, the results of DNA sequencing are small sequences called reads or fragments. Due to the difficulty of assembling the full genome from reads, a reference genome is not always available for a species. For this reason, reference-free algorithms which do not use a reference genome are useful for poorly understood genomes.
A common variation between the chromosomes in a homologous group is the single nucleotide polymorhpism (SNP), where the sequences differ by exactly one nucleotide at a location. Genomes are sometimes represented as a consensus sequence and a list of SNPs, without information about which variants of a SNP belong in which chromosome. This discards useful information about the genome.
Identification of variant compositions aims to correct this. A variant composition is an assignment of the variants in a SNP to the chromosomes. Identification of variant compositions is closely related to haplotype assembly, which aims to solve the sequences of an organism's chromosomes, and variant detection, which aims to solve the sequences of a population of bacterial strains and their frequencies in the population.
This thesis extends an existing exact algorithm for haplotype assembly of diploid species (Patterson et al, 2014) to the reference-free, polyploid case. Since haplotype assembly is NP-hard, the algorithm's time complexity is exponential to the maximum coverage of the input. Coverage means the number of reads which cover a position in the genome. Lowering the coverage of the input is necessary. Since the algorithm does not use a reference genome, the reads must be ordered in some other way. Ordering reads is an NP-hard problem and the technique of matrix banding (Junttila, PhD thesis, 2011) is used to approxiately order the reads to lower coverage. Some heuristics are also presented for merging reads. Experiments with simulated data show that the algorithm's accuracy is promising. The source code of the implementation and scripts for running the experiments are available online at https://github.com/maickrau/haplotyper.
