PUB - Publikationen an der Universität Bielefeld

This work is divided into two distinct and (almost) unrelated parts. The first, more practical, focuses on biological applications for de Bruijn subgraphs, while the second, more theoretical, presents a study on Interval Group Testing in the presence of erroneous test outcomes. Although the subjects of both parts are from the computational viewpoint completely distinct, their motivations are closely related: while the study of de Bruijn subgraphs was motivated by the identification of unique sequences for a better design of DNA probes, the study of the effect of errors in Interval Group Testing was motivated by the error produced by badly designed probes. In the first part of this thesis, we present a method for constructing compact representations of de Bruijn subgraphs without passing through the usual memory expensive step of constructing the graph in its traditional form. We further analyze the use of this compact representation in three different applications: marking repeated sequences in a set of reads, identifying new repeat families in incompletely sequenced genomes, and creating splicing graphs for a collection of transcripts. The second part of this text is dedicated to Interval Group Testing. Group testing is an approach for reducing the number of tests needed for identifying few elements with some rare property in a large group. Group testing finds a lot of applications in many different fields, for instance, in identifying people infected with HIV or syphilis in large populations, finding faulty unities in computer networks, or finding points in mature RNAs where introns were spliced out. The last application motivates a variant called Interval Group Testing. The traditional Interval Group Testing cannot deal with experimental errors, which cannot be ignored in a real life application. Therefore we present bounds on the number of tests needed for identifying the elements of interest when an upper bound on the number of errors in the tests' outcomes is allowed.