[PDF] Supplementary Materials for Fast genotyping of known SNPs

View - Download Supplementary Materials for Fast genotyping of known SNPs

Previous PDF

Next PDF

Supplementary Materials for Fast genotyping of known

SNPs through approximatek-mer matching

Ariya Shajii, Deniz Yorukoglu, Y. William Yu, & Bonnie Berger

A Algorithms

Note, we will only write QUERY(Dref;K) and QUERY(DSNP;K) to represent queries inDrefand D

SNP, respectively;JrefandJSNPare implied.Input:R

Output:Dref

D ref fg; fori2 f1;2;:::;length(R)k+ 1gdo D ref.append((R[i:i+k];i));fappend (k-mer, index) tupleg sort(Dref);fsort by(k-mer)g uniq(Dref);fonly keep one instance of eachk-mer (which to keep is unimportant)g returnDref;Algorithm S.1: Generation of reference dictionaryDreffrom reference sequenceR.Input:Dref

Output:Jref

J ref [0;0;:::;0]2N232;ffor simplicity, assumeJrefis 0-indexedg u prev 0; fori2 f1;2;:::;length(Dref)gdo K;V Dref[i];fKis the 32-mer,Vis its index in the referenceg u ((K)32); ifu6=uprevthen forj2 fuprev+ 1;uprev+ 2;:::;ugdo J ref[j] i; u prev u; fori2 fuprev+ 1;uprev+ 2;:::;2321gdo J ref[i] length(Dref) + 1; returnJref;Algorithm S.2: Generation of secondary hash tableJreffrom reference dictionaryDref.

Corresponding author: bab@mit.edu

AB

01AA+ 12

32

1CDBEFJ

ref:D

ref:Binary search to ndBFigure S.1: Simplied visualization of queryingDrefwith some 32-mer. The encoded 32-mer has high bits

A(red) and low bitsB(blue). We look intoJrefat indicesAandA+1 to obtain the bounds for our search inDref. Then, sinceDrefis sorted by the numerical values of the encoded 32-mers, we perform a binary

search on this interval for the 32-mer whose encoding has low bitsB. Since all 32-mers in the interval

have high bitsA(by design ofJref), once we nd an encoding with low bitsB, we know we have found our initial 32-mer in the dictionary.Input:Dref;Jref;K

Output:QUERY(Dref;Jref;K)

u b(K)=232c; a Jref[u]; ifa >length(Dref)then returnNull; ifu <232then b Jref[u+ 1]; else b length(Dref) + 1;

returnDref[a:b].bsearch(K);fbinary search froma(inclusive) tob(exclusive)gAlgorithm S.3: Querying ofDrefwith some 32-merK.

2

Input:DSNP

Output:P

P Array(length = maxfV:index : (K;V)2DSNPg);

for(K;V)2Drefdo p V:index;

P[p]:refallele V:refallele;

P[p]:altallele V:altallele;

P[p]:refallelefreq V:refallelefreq;

P[p]:altallelefreq V:altallelefreq;

P[p]: 0;

P[p]: 0;

returnPAlgorithm S.4: Initialization ofP.Input:Dref;DSNP;Q

Output:TARGET(Dref;DSNP;Q)

indices Array(); kmers Array(); for(K;oset)2 S(Q)do forK02 N(K)do V

1 QUERY(Dref;K0);

V

2 QUERY(DSNP;K0);

ifV16= Nullthen indices:append(V1oset); kmers:append((K0;V1oset)); ifV26= Nullthen indices:append(V2:indexoset); kmers:append((K0;V2:indexoset)); target highestmultiplicityelement(indices);

return(target;kmers);Algorithm S.5: Finding target index in reference sequence at which read likely originated. Assume \high-

estmultiplicityelement" returns the element of highest multiplicity in its argument array if said element

is unique and has multiplicity greater than one, and returns Null otherwise. This can, in practice, be

implemented in linear runtime using a hash table that maps indices to frequencies. Note that, in Algorithm S.5, we must always check the following two conditions for eachk-mer K

02 N(K) that we query before adding the results of this query to our array of potential target

indices: Based on the results of theDrefquery,K0must not: dier fromKin a position where there exists a SNPandhave the alternate allele for that SNP. Based on the results of theDSNPquery,K0must not: dier fromKin a position where there exists a SNPandhave the reference allele for that SNP. 3 These two conditions prevent us from changing what is actually the alternate allele of a SNP in a read to the reference allele (viaN(K)) and incorrectly obtaining a successful query result inDref, or vice versa forDSNP.Input:Dref;DSNP;Q;P

Output:{

target;kmers TARGET(Dref;DSNP;Q); for(K;normalizedindex)2kmersdo ifnormalizedindex = targetthen fori2 f1;2;:::;kgdo ifP[target +i1]6= Nullthen ifK[i] =P[target +i1]:refallelethen

P[target +i1]: P[target +i1]:+ 1;

else ifK[i] =P[target +i1]:altallelethen P[target +i1]: P[target +i1]:+ 1;Algorithm S.6: Updating pileup table for readQ.

B Full Experiment Timings

Table S.1: Full LAVA timing results compared to other genotyping pipelines, corresponding to Fig. 4 in

the main text. All times are given in minutes.Method Mapping Indexing/Sorting Genotyping Total Time

LAVA (dbSNP) 0 0 294.4 294.4

LAVA (Ay) 0 0 184.8 184.8

LAVA Lite (dbSNP) 0 0 367.7 367.7

LAVA Lite (Ay) 0 0 247.0 247.0

Bowtie 2 + mpileup (dbSNP) 781.3 68.6 446.1 1296.0

Bowtie 2 + mpileup (Ay) 781.3 68.6 446.1 1296.0

BWA + mpileup (dbSNP) 1193.9 68.6 437.5 1700.0

BWA + mpileup (Ay) 1193.9 68.6 437.5 1700.0

Bowtie 2 + GATK HC (dbSNP) 781.3 0 456.1 1237.4

Bowtie 2 + GATK HC (Ay) 781.3 0 211.8 993.1

BWA + GATK HC (dbSNP) 1193.9 0 585.7 1779.6

BWA + GATK HC (Ay) 1193.9 0 223.9 1417.8

SNAP + GATK HC (dbSNP) 129.2 43.5 816.4 989.1

SNAP + GATK HC (Ay) 129.2 43.5 227.4 400.14

quotesdbs_dbs17.pdfusesText_23

[PDF] uprev rom editor

[PDF] uprev tuning guide

[PDF] ups api example

[PDF] ups canada zip code lookup

[PDF] ups door to door

[PDF] ups hubs map

[PDF] ups import zones

[PDF] ups map for shipping

[PDF] ups postal code finder

[PDF] ups remote area list 2020

[PDF] ups supply chain solutions container tracking

[PDF] ups supply chain solutions inc tracking

[PDF] ups supply chain solutions pars tracking

[PDF] ups supply chain solutions shipment tracking

[PDF] ups tracking map app