2026-07-22T03:56:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1674 2024-03-06T11:08:10Z ddc:004 open_access

Storage and Retrieval of Individual Genomes Mäkinen, Veli Navarro, Gonzalo Sirén, Jouni Välimäki, Niko Pattern matching text indexing compressed data structures comparative genomics A repetitive sequence collection is one where portions of a emph{base sequence} of length $n$ are repeated many times with small variations, forming a collection of total length $N$. Examples of such collections are version control data and genome sequences of individuals, where the differences can be expressed by lists of basic edit operations. Flexible and efficient data analysis on a such typically huge collection is plausible using suffix trees. However, suffix tree occupies $O(N log N)$ bits, which very soon inhibits in-memory analyses. Recent advances in full-text emph{self-indexing} reduce the space of suffix tree to $O(N log sigma)$ bits, where $sigma$ is the alphabet size. In practice, the space reduction is more than $10$-fold for example on suffix tree of Human Genome. However, this reduction remains a constant factor when more sequences are added to the collection We develop a new self-index suited for the repetitive sequence collection setting. Its expected space requirement depends only on the length $n$ of the base sequence and the number $s$ of variations in its repeated copies. That is, the space reduction is no longer constant, but depends on $N/n$. We believe the structure developed in this work will provide a fundamental basis for storage and retrieval of individual genomes as they become available due to rapid progress in the sequencing technologies. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Veli Mäkinen and Gonzalo Navarro and Jouni Sirén and Niko Välimäki 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08261.10 urn:nbn:de:0030-drops-16743 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.10 eng https://creativecommons.org/licenses/by/4.0/legalcode