Zusammenfassung Motivation Die Identifizierung von Dokumenten in einer großen Datenbank, die eine Abfragesequenz enthalten, ist ein grundlegendes Problem in der Informationsretrieval und der computergestützten Biologie. Wir konzentrieren uns auf die ungefähre Version dieses Problems für genomische Sequenzen: Die Ergebnismenge kann falsche positive Übereinstimmungen enthalten, jedoch keine falschen Negativen. Lösungen auf dem neuesten Stand der Technik basieren auf Bloom-Filtern, um alle k-mers (Substring von fester Länge k) in den Dokumenten zu indexieren. Um eine Abfrage zu beantworten, werden Dokumente zurückgegeben, die mindestens einen von den Nutzern vorgeschriebenen Anteil an Abfrage-k-mers (typischerweise 75–80%) teilen. Methoden und Ergebnisse Hier untersuchen wir ein alternatives Indexdesign, das auf k-mer-Mindestwerten und Ganzzahlkompressionsmethoden basiert. Wir zeigen, dass eine sorgfältige Implementierung dieses Designs frühere Lösungen auf der Basis von Bloom-Filtern deutlich übertrifft: Der Index hat einen geringeren Speicherbedarf und schnellere Abfragezeiten, während falsche positive Übereinstimmungen nur einen geringen Einfluss auf das Ranking der angegebenen Dokumente haben. Dieser Trend ist robust über genomische Datensätze unterschiedlicher Komplexität und Abfragelasten. Software Die Software ist kostenlos unter github.com/yhhshb/kaminari unter der MIT-Lizenz verfügbar. Reproduzierbarkeitsskripte sind verfügbar unter github.com/vicLeva/benchmarksₖaminari.
Levallois et al. (Wed,) haben diese Frage untersucht.