Detta dokument introducerar en ny metod, kallad Reference-Based String Alignment (RBSA), som snabbar upp hämtning av optimal subsekvens matchar i stora databaser av sekvenser under redigeringsavståndet och Smith-Waterman likhetsmåttet. RBSA fungerar med antagandet att den optimala matchningen avviker med en relativt liten mängd från frågan, ett belopp som inte överstiger en förspecificerad del av frågelängden. RBSA har en exakt version som garanterar inga falska uppsägningar och kan hantera stora frågor effektivt. En ungefärlig version av RBSA beskrivs också, som uppnår betydande ytterligare förbättringar jämfört med den exakta versionen, med försumbara förluster i hämtning noggrannhet. RBSA utför filtrering av kandidatmatcher med hjälp av förutbestämda inställningspoäng mellan databassekvensen och en uppsättning referenssekvenser med fast längd. Vid frågetillfället delas frågesekvensen upp i längdsegment som är lika med referenssekvensernas. För vart och ett av dessa segment används anpassningspoängen mellan segmentet och referenssekvenserna för att effektivt identifiera ett relativt litet antal kandidatsekvensmatcher. Ett alfabet kollapsning teknik används för att förbättra beskärning kraften i filtersteget. I vår experimentella utvärdering, RBSA betydligt överträffar state-of-the-art biologiska sekvens anpassningsmetoder, såsom q-gram, BLAST, och BWT.
Till exempel filtrerar REF [30] resultaten till en frågesekvens genom att använda förkomputerat avstånd mellan sekvenser i databasen och en uppsättning referenssekvenser.
Reference-Based Alignment in Large Sequence Databases
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}