De Bruijn grafen G K av en uppsättning strängar S är en viktig datastruktur i genom montering som representerar överlappningar mellan alla K-längd substrängar av S. Konstruktion och navigering av grafen är ett utrymme och tid flaskhals i praktiken och det främsta hindret för montering av stora genom. Detta problem förvärras eftersom state-of-the-art monteringsföretag inte bygga de Bruijn grafen för en enda ordning (värde av K) men för flera värden av K: de bygger d de Bruijn grafer, var och en med en specifik ordning, dvs, G K 1, G K 2,. .., G K d. Även om detta paradigm ökar kvaliteten på monteringen producerar men det kraftigt ökar körtiden, på grund av behovet av att konstruera d grafer i stället för en. I denna artikel visar vi hur man kan förstärka en koncis de Bruijn graf representation av Bowe et al. (Proc. WABI, 2012) för att stödja nya operationer som låter oss ändra ordningen i farten, effektivt representera alla de Bruijn grafer av ordning upp till något maximum K i en enda datastruktur. Våra experiment visar vår variabel ordning de Bruijn graf endast blygsamt ökar rymdanvändning, byggtid och navigeringstid jämfört med en enda ordning graf.
REF utökade denna datastruktur för att bygga en representation som för ett givet värde av K konstruerar alla k 0 th-order de Bruijn-grafer, där k 0 K, med endast två gånger det utrymme som behövs för att konstruera Kth-order de Bruijn-grafen.
Variable-Order de Bruijn Graphs
{'venue': '2015 Data Compression Conference', 'journal': '2015 Data Compression Conference', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Biology']}