Den nya generationen genomiska tekniker har gjort det möjligt för forskare att bestämma det kollektiva DNA av organismer (t.ex. mikrober) samexisterande som samhällen i hela ekosystemet (t.ex., inom den mänskliga värden). Det finns ett behov av beräkningsmetoder för att analysera och kommentera de stora volymerna av tillgängliga sekvensdata från sådana mikrobiella samhällen (metagenomer). I det här dokumentet har vi utvecklat en effektiv och exakt metagenome-klustermetod som använder lokalhetskänslig hashteknik (LSH) för att uppskatta den beräkningskomplexitet som är förknippad med att jämföra sekvenser. Vi introducerar användningen av fast längd, gapless subsequences för att förbättra känsligheten för LSH-baserade likhetsfunktionen. Vi utvärderar prestandan av vår algoritm på två metagenome dataset i samband med microbes som finns på olika mänskliga hud platser. Våra empiriska resultat visar styrkan i det utvecklade tillvägagångssättet i jämförelse med tre toppmoderna sekvensklustringsalgoritmer med avseende på beräkningseffektivitet och klusterkvalitet. Vi visar också praktisk betydelse för den utvecklade klusteralgoritmen, för att jämföra bakteriemångfald och struktur mellan olika hudplatser.
I vårt tidigare arbete utvecklade vi MC-LSH REF, som använder en effektiv lokal känslig hashfunktion för att approximera de pairwise sekvensoperationerna.
Efficient Clustering of Metagenomic Sequences using Locality Sensitive Hashing
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}