Improving the Compact Bit-Sliced Signature Index COBS for Large Scale Genomic Data

In this thesis we investigate the potential for improving the Compact Bit-Sliced Signature Index (COBS) [BBGI19] for large scale genomic data. COBS was developed by Bingmann et al. and is an inverted text index based on Bloom filters. It can be used to index k-mers of DNA samples or q-grams of plain text data and is queried using approximate pattern matching based on the k-mer (or q-gram) profile of a query. In their work Bingmann et al. demonstrated a couple of advantages COBS has over other state of the art approximate k-mer-based indices, some of which are extraordinary fast query and construction times, but as well as the fact that COBS can be constructed and queried even if the index does not fit into main memory. ... mehrThis is one of the reasons we decided to look more closely at some areas we could improve COBS. Our main goal is to make COBS more scalable. Scalability is a very important factor when it comes to handling DNA related data. This is because the amount of sequenced data stored in publicly available archives nearly doubles every year, making it difficult to handle even from the perspective of resources alone. We focus on two main areas in which we try to improve COBS. Those are index compression through clustering and distribution. The thesis presents our findings and improvements achieved in respect to those areas.

In dieser Arbeit untersuchen wir verschiedene Möglichkeiten den kompakten bit-transponierten Signaturindex COBS [BBGI19] bei der Anwendung für Genomdatenbanken zu verbessern. COBS wurde von Bingmann et al. entwickelt und ist ein invertierter Textindex basierend auf Bloomfiltern. Der Hauptanwendungsbereich von COBS ist die Indizierung von Nukleotidfolgen die durch DNA-Sequenzierung gewonnen wurden. Er kann jedoch auch als allgemeiner Textindex benutzt werden. COBS beantwortet Anfragen durch einen approximativen Musterabgleich indem er sich die k-mer (oder q-gram) Profile der Anfragen zu nutze macht. ... mehrBingman et al. haben in ihrer Arbeit gezeigt das COBS einige Vorteile gegenüber Ansätzen hat, die dem Stand der Forschung im Bereich k-mer basiertes approximatives Textindizieren entsprechen. Einige von den Vorteilen sind sehr schnelle Konstruktion und Bearbeitung von Anfragen, sowohl die Möglichkeit den Index zu Konstruieren wenn dieser nicht im Hauptspeicher passt. Aus diesen Gründen, die sich zunächst vielversprechend anhören, haben wir uns entschlossen anzuschauen wie man COBS verbessern könnte. Das Hauptziel dieser Arbeit ist COBS skalierbar zu machen. Skalierbarkeit ist eine wichtige Eigenschaft eines Textindexes der mit großen Datenmengen umgehen muss. Die Größe von öffentlich verfügbaren Genomdatenbanken verdoppelt sich fast jedes Jahr. Dies ist insbesondere problematisch aus der Sicht von Resourcen die ein Rechner zu bieten hat, weil diese schnell an ihre Grenzen stoßen. In dieser Arbeit fokusieren wir uns auf zwei Aspekte die das Ziel haben COBS zu verbessern. Dies sind Indexkomprimierung durch Clustering und die Entwicklung einer verteilten COBS Variante.