Bakgrund: De Bruijn grafens datastruktur används i stor utsträckning i nästa generations sekvensering (NGS). Många program, t.ex. De novo Assemblers, förlita sig på in-minne representation av denna graf. Nuvarande tekniker för att representera de Bruijn-grafen av ett mänskligt genom kräver dock en stor mängd minne (≥ 30 GB). Resultat: Vi föreslår en ny kodning av de Bruijn grafen, som upptar en storleksordning mindre utrymme än nuvarande representationer. Kodningen är baserad på ett Bloom filter, med en ytterligare struktur för att ta bort kritiska falska positiva. Slutsatser: En monteringsprogram som implementerar denna struktur, Minia, utförde en komplett de novo montering av mänskliga genom kortläsningar med 5,7 GB minne i 23 timmar.
Med utgångspunkt i denna probabilistiska representation introducerar REF en exakt de Bruijn Graph-representation som parar ihop en Bloom-filterbaserad ungefärlig de Bruijn-graf med en exakt tabell med kritiska falska positiva kanter.
Space-efficient and exact de Bruijn graph representation based on a Bloom filter
{'venue': 'Algorithms for Molecular Biology', 'journal': 'Algorithms for Molecular Biology', 'mag_field_of_study': ['Computer Science', 'Medicine']}