ABSTRACT Optimering av utsädesval är ett viktigt problem i läskartläggningen. Antalet icke-överlappande frön en mappare väljer bestämmer känsligheten hos mappen medan den totala frekvensen av alla utvalda frön bestämmer hastigheten på mappen. Moderna så-och-utöka mappare väljer oftast frön med antingen en lika lång och fast längd schema eller med en oflexibel placering, som båda begränsar potentialen för mapparen att välja mindre frekventa frön för att påskynda kartläggningsprocessen. Därför är det viktigt att utveckla en ny algoritm som kan justera både den individuella utsädeslängden och utsädesplaceringen, samt härleda mindre frekventa frön. Resultat: Vi presenterar Optimal Seed Solver (OSS), en dynamisk programmeringsalgoritm som upptäcker de minst frekvent förekommande x-kärnorna i en L-bp-avläsning i O(x × L)-operationer i genomsnitt och i O(x × L 2 )-operationer i värsta fall. Vi jämförde OSS mot fyra toppmoderna system för utsädesval och konstaterade att OSS ger en trefaldig minskning av den genomsnittliga utsädesfrekvensen över de bästa tidigare optimeringarna av utsädesval. Tillgänglighet: Vi tillhandahåller en implementering av Optimal Seed Solver i C på: https://github.com/CMU-SAFARI/Optimal-Seed-Solver
Den optimala frölösaren (OSS) algoritmen REF tillhör denna typ.
Optimal Seed Solver: Optimizing Seed Selection in Read Mapping
{'venue': 'Bioinformatics, Jun 1;32(11):1632-42, 2016', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Biology', 'Medicine']}