Motivering: Nyligen genomförda experimentella studier på komprimerade index (BWT, CSA, FM-index) har bekräftat deras praktiska för att indexera mycket långa strängar såsom det mänskliga genomet i huvudminnet. Ett BWT-index för människans genom (med omkring 3 miljarder tecken) upptar till exempel omkring 1 G byte. Dessa index är dock utformade för exakt mönstermatchning, vilket är för strikt för biologiska tillämpningar. Efterfrågan är ofta att hitta lokala anpassningar (par av liknande understrängar med tillåtna luckor). Utan indexering kan man använda dynamisk programmering för att hitta alla lokala anpassningar mellan en text T och ett mönster P i O(jTjPj) tid, men detta skulle vara för långsamt när texten är av genomskala (t.ex. Att anpassa en gen till det mänskliga genomet skulle ta tiotals till hundratals timmar). I praktiken använder biologer heuristisk-baserad programvara som BLAST, som är mycket effektiv men inte garanterar att hitta alla lokala anpassningar. Resultat: I den här artikeln visar vi hur man bygger en programvara som heter BWT-SW som utnyttjar ett BWT-index i en text T för att påskynda den dynamiska programmeringen för att hitta alla lokala anpassningar. Experiment visar att BWT-SW är mycket effektivt (t.ex. Att anpassa ett mönster av längd 3 000 till det mänskliga genomet tar mindre än en minut). Vi har också analyserat BWT-SW matematiskt för en enklare likhetsmodell (med luckor ej tillåtna), och vi visar att den förväntade körtiden är O(jTj 0.628 jPj) för slumpmässiga strängar. Så vitt vi vet är BWT-SW det första praktiska verktyget som kan hitta alla lokala anpassningar. Ändå är BWT-SW inte tänkt att vara en ersättning av BLAST, eftersom BLAST är fortfarande flera gånger snabbare än BWT-SW för långa mönster och BLAST är verkligen korrekt nog i de flesta fall (vi har använt BWT-SW för att kontrollera mot noggrannheten hos BLAST och fann att endast sällan BLAST skulle missa några betydande justeringar).
BLAST är dock ett ungefärligt tillvägagångssätt som inte skulle kunna garantera att hitta alla lokala anpassningar även om BLAST verkligen är tillräckligt korrekt i de flesta fall REF.
Compressed indexing and local alignment of DNA
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}