Exploring de Bruijn graph construction with Bloom filters

Abstract

DNA samskeiting er reiknifræðilega erfitt verkefni og ýmsar aðferðir hafa verið gefnar út. Flestar þeirra nota svokölluð de Bruijn net (DBG). Ein áskorunin við DNA samskeitingu er sú staðreind að villur í inntakinu auka mjög stærðina á netinu. Flestar villurnar koma fyrir í k-merum sem koma bara einu sinni fyrir í inntakinu. Við notum aðferð sem síar þessa k-mera í burtu og komum þannig í veg fyrir að þeir endi í netinu. Þessi aðferð notar Bloom síur til að sía í burtu villurnar og er því nefnd BFAdder. Gallinn við að nota Bloom síur er sá að það er möguleiki á fölskum jákvæðum.Við sýnum að með því að nota BFAdder tekst okkur að sía í burtu mikinn meirihluta af k-merum á sama tíma og við viðhöldum háu hlutfalli af k-merum úr erfðamenginu í netinu. Við kynnum til sögunnar tvær uppfærslur á BFAdder þegar meðaltals k-mer coverage fer yfir ákveðið gildi fyrir hvora uppfærslu. Með því að nota uppfærslurnar náum við enn meiri samdrætti í fjölda k-mera á kostnað lækkaðs hlutfall af k-merum úr erfðamenginu. Við sýnum hins vegar fram á að með því að velja vel gildin á uppfærslurnar þá næst að draga úr þessum samdrætti í hlutfalli.