All right, so hello everyone again. We're gonna start with my report, which is on the crypto 2016 puzzle solution and prizes to selected winners. So if you didn't get your solution in by now, I'm about to reveal the solution. If you don't wanna hear it, run outside for a couple minutes, but let's go through it. So this was the piece of the text that was included in your packet that said use the GIFs in your registration packet to determine the real security quotation, and let's talk about what it was that you received. First, you got a T-shirt, and this is the back of the T-shirt, and it has a number of quotations on it, and it has some symbols at the beginning and the end of each quotation. And if you zoom in on that, you saw a little film strip. That was supposed to clue folks that these were somehow film or movie related.  Well, because in addition to being general chair of this conference, I'm also president of the board of directors of the Seattle International Film Festival, which is the largest film festival in North America and runs for 25 days in Seattle from late May to mid June, and if you're ever in Seattle, please come to the film festival. So I thought that a film-themed, security-themed puzzle was appropriate, and I should, before I proceed further, acknowledge Josh Benelow. Josh and I worked on this jointly, and the two of us put this together for all of you to enjoy. So would clever and please kind of thank Josh. Okay. So, there's movie quotes. There is this thing now called the internet, so you don't have to actually know all these movies in your head, but if you go and look them up or happen to know them, you would find that the movies that these quotes came from often had a security-related theme, imitation game, Ghostbusters didn't, although it was about containment, sneakers, hackers, inception, space balls, and my personal favorite Blade Runner which had to make it into the puzzle. Now the second thing on the shirt was that symbol down in the lower right, which was the picture of the wine bottle highlighting the little round thing in the lower right of the label. And then you got a wine bottle with a custom label on it. This is backdoor red or backdoored wine, and my thanks to Michael Moniz of Liberton Hotels in Toronto who did the graphic design for me as a favor of the label. Again, Josh and I gave a basic design. And if you look at that symbol on the label, it says that, which is a key to understanding how to unlock the puzzle. It's a very simple substitution cipher. You take the key, you take the first letters of the films, and remember there was a hint that the is an insignificant, can be an insignificant word, so you didn't look for the T in the imitation game, but the I. And when you translate that, you get theater, which completes the security, should not be confused with theater, also a reference back into film. Okay, so that was the puzzle. We got 15 correct submissions. I want to acknowledge everybody on here who got a correct submission and got inserted in by four o'clock. I particularly want to highlight Shai Halevi's children, Gil and Sharon Halevi, who got a solution. These are in order of submission. So they were the third correct solution submitted and the youngest submitters. Okay? Now, of these 15, I have randomly selected or Excel's random number generator randomly, and if you randomly selected three people to win prize, I have real prizes up here for three of these people. And with Marshall Ball, Jeremy Jean, and Aaron Traumer, please come up to receive prizes for correctly solving the puzzle. So they are identical. So Aaron, there you go. Congratulations. Marshall, there you go. Congratulations. There you go.  You're most welcome. I'm glad you enjoyed it. And with that, that concludes my report on the crypto 2016 puzzle. Thank you, Ryan. Thank you, Ryan. So I hope the prize winners enjoy their back doors to run and the number generators that they're getting as prizes. And I'd like to invite Matt Robchott to take the stage. Next on stage is Bar Perniel. If Bar could get ready. Thank you, Matt. Just to remind people that please come and sit. And if there's too many people standing, there's an additional room in the multimedia pavilion.  We really don't want that to happen. So please take a seat or go to the overflow theater. Thank you, Matt. Okay, so good evening. It's traditional to start the rump session with a report from the program chairs behind the scenes on the submission and review process. It's my pleasure to provide that for crypto 2016. We received a new record. So in the spirit of the Olympic rump session, we have a new record to report. 282 submissions reduced to 275 after withdrawals. We accepted 70 for the program, which represents roughly a 25% acceptance rate. And here we see the historical acceptance rate over the last 24 years. So we're back to the levels we were seeing before the year 2000. Crypto now is getting up to around about 1,000 reviews. And given that a paper length can be up to 30 pages, that's an enormous amount of reviewing. So we had a very dedicated and hard-working program committee that went through all of this work. So thank you to all of them. We also had 320 external reviewers involved. So many of you will be in this room. Thank you very much for your contributions. Again, in the Olympic spirit, we can call out some nation contributions. So there were six countries that provided at least 5% of the submissions. France, US, Israel, China, Japan, and Germany. And this translated through, so 65% of the submissions from these countries alone, translating into 71% of the final accepted submissions in your program. Of course, there's different ways to measure cryptographic productivity. And the gold medal for the best use of available landmass goes to Singapore with one paper for every 350 kilometer square. So the rump session marks the halfway point of crypto 2016. So you're probably already thinking about next year and maybe making some submissions. So it's worth doing a little data mining to see what we might learn from this year. So the number of co-authors, I've presented here the acceptance rate for papers with single-author papers here. You can see it's very hard to get a single-author paper accepted. So congratulations to those that achieve that. And as we add authors, things get progressively better. You get a higher acceptance rate until basically after four it drops off. Probably a little bit too much partying takes place. So it seems that four is a good number for the number of co-authors. You also want to think about your first impressions, the title, because remember, the reviewers are gonna make a bid for your paper to review your paper. So it's probably interesting to look at how you structure your title to the paper. And Short and Piffy certainly wins the day. So titles that could be characterized as Short and Piffy had an above average acceptance rate of 30%. Now what's interesting is that you don't wanna get caught in this kind of no man's land of middle-length titles. It turns out if you just keep piling in the words, you can actually move on to something that's not short and not a tall Piffy. And you'll find you have pretty much the same acceptance rate at the end of the day. So Short or Long, one or the other. What about some of the words? Were there any interesting keywords? So the committee liked the following words in the title. So a green thumbs up means papers or submissions with these words in the title had an above average chance of being accepted. So practical, efficient, and cryptanalysis. The money word for crypto 2016 though was applications. That had a very high acceptance rate. So that's kind of interesting for next year perhaps. On the other side, which were the words that didn't quite capture the program committee's imagination. Well, somewhat controversially for a crypto conference I think, encryption didn't do well and really quite disturbingly new didn't do quite so well either. So anyway, hindsight's a wonderful thing and we can construct what would have been an ideal title for crypto 2016. Oh, I forgot, I'm so sorry. Let me go on. Some people like to punctuate their title. Makes it a bit more interesting, a bit more subtle, a bit more considered. So the committee liked parentheses. I get a little thumbs up there, so above average acceptance rate. The committee went bananas over colons. Colons were very popular. But the question mark, maybe it implies a little indecision or something for some reason that didn't quite capture the imagination of the program committee. So bringing all this together, we can come up with what would have been the ideal crypto 2016 title as I say with hindsight. And this would have been a good title. A efficient crypto analysis, colon. No practical impremises, applications are secure. And it would of course have been by four authors. So I'm the one talking, but crypto relies on the contributions of many. So a big thank you to John and Brian, my program co-chairs and Brian, the general chair, pleasure to work with you. The excellent hardworking program committee, all the sub-reviewers, and most importantly everyone who submitted to crypto 2016. And I hope you enjoy the Rump session. Okay, so next up we have something about Feng Shui by somebody called Bart Praniel and Nigel Smart come to the stage please. And could somebody bring me a beer that would be really appreciated. So the interesting thing to note is that of course everybody knows that Bart is the ex-president of the ISR. So unsurprisingly his favorite discipline is hammer throwing. Well, this is a plug for a use next paper, but clearly this title would never have made it to crypto. So there was in fact way too many authors. And the theme I chose was indeed hammer throw because I was thinking of Field Hockey, but today actually the Netherlands beat, was beaten by Belgium in Field Hockey. So I guess Martijn would have rejected my paper if I did. So I didn't take any risks there. So it's a very confusing title where many authors, we each chose a word and then we put it together and somehow it got into a use next. So what would we really do? Okay, this. We broke RSA in the cloud. So how does it work? We use some very simple ideas and some simple crypto machinery, but very clever software stuff. Don Mime called us at the University of Amsterdam. So we used actually two basic building blocks. One is Rohammer, and I hope you all know that Kenny is Scottish. So I knew he actually would accept this paper with those beautiful pictures of Scottish people. So Rohammer is a very cool trick in which you can actually flip bits in DRAMM as a consequence of higher densities in DRAMM by reading repeatedly at jacquard rows. So you never have to write in the memory, you just read a lot, and at some moment you flip bits in the middle row. So now you already understand why there is flip in the title and why there is hammer in the title and why I chose the hammer throw. Okay, so it's a bit tricky to find out actually if you're in the cloud which bits flip. And the practical guys from our team, they spent about 10 minutes of effort to find one bit flip that works. So this is why we don't use hammer and hammer throw bit flips and you can't completely control the location. Next thing is memory duplication. So what happens in the cloud, you actually can rent your machines with the cloud providers and actually they try to be efficient. And using this an attacker can actually map the physical memory page of the victim virtual machine to the attacker virtual space. The scenario is that somebody has a cloud instance which you want to attack. So you actually also make a cloud instance and then from your cloud instance you're gonna attack the keys of the other guy. And how do you do it? Based on duplication and the factory part is because we have to neatly arrange memory in a harmonic way to actually get to do it. And this explains the factory part of the title. So how does it work? Very simple, you have this blue virtual machine, you have the victim, so you do host, you have the victim having his machine, the attacker having his machine and so each has their own physical memory at the bottom. And so what you do as an attacker is you put content in your virtual machine which likely the attacker will also have. Can be a list of keys that's public, public keys of course, or maybe some other things, in this case the picture. And so what will happen in the cloud is actually that the cloud will want to be efficient. What they will do is they will actually spot duplication, it will save memory and put it together with pointers. The next thing is if you then start flipping bits in your virtual machine using row hammer, what will happen in the physical memory, it will be updated and you actually now flip the memory of the victim. Without doing anything, you don't have to violate any of the access control rules of the cloud.  So what can you do in practice? Somebody is running open SSH in this cloud instance, you start SSH session with the wrong key, doesn't matter. What the victim will do is read the authorized key file with an RSA modulus, you now do your row hammer bit flip and you flip a bit of the modulus. There's no longer an RSA modulus, it's now a random integer of 4,000 bits, that turns out to be easy to factor. So the method we use to add a elliptic curve, elliptic curve factorization depends on the second largest prime factor. And there is good statistics about this, we know that on average it's about 20% of the size of the modulus. So, and if you're lucky of course, it's even much smaller. That's it more or less, we used stammer tool, it's the wrong sport I guess, but okay. So, 10 to 4 bit bodily, you can see we can factor almost all of them with 10 bit flips. What we used was about one hour time on a big cluster, 64 gigabyte RAM, then we stopped, we abandoned if we couldn't make that. We got 48 bit, we could do more, a bit less, but we could still get very close to all of them with 30 bit flips and then 50 bit flips we got up to 80% of all 4,096 bit module. And of course this was tried on real cloud instances, really in the cloud, we made this work in practice. Of course we did warn the cloud providers in advance that they should implement countermeasures against this attack. Similar thing on GPG, you can actually use the Abbit mechanism in DB and Ubuntu, the APT. You first modify the sources list, so in fact malware will be downloaded rather than from the real URL. At the moment of the signature checking you actually flip the RSA keys. The trusted GPG file, you factor again until you're forced to signature and now install malware in the victims machine. Again, you factorize and that's it. So we also extend to the DV Helman. The problem there is that your publicly available software for this read log is not as good as the others factoring. So we didn't get as far for DV Helman as for RSA, but the paper has the technical details. We also discussed mitigations and if you want to find the paper, it's on there. Thank you very much for your attention. Thanks, Bart. Would Jeremiah please come to the stage and next up we have Nigel Smart. Just let's say there's loads of seats down here for those standing. Oh yeah, thanks Nigel. Please come and sit down, otherwise we'll get shut down. Yeah, come please, if you're standing, please come sit here. We have to otherwise the rump session will be shut. Right. Okay, whoops, what happened there? What? Just advanced. Oh, there we go. No, what's my talk? Advanced. Advanced. What, what, what? Have you, if you can meet him wrong? Uh-oh. Uh-oh. Uh-oh.  Let's unwind and we'll have Jeremiah and we'll do something to fix Nigel's talk at some point. Thanks for your understanding, Nigel. Great talk. Great talk. All right, thanks everyone. Like to give you a quick update on the Crip Olympic Games, which as you know are taking place right now. And I want to talk about my favorite event, which is password frequency list disclosure. So, there we go. So, some of you may be unfamiliar with this exciting event. So how does it work? Contestants start by collecting a large dataset of user passwords. And then they produce a histogram, which is just a plot of the frequency of the most popular passwords. And finally, the goal is to release a frequency list, which can be obtained by simply removing the passwords and just outputting the associated frequencies. And contestants may perturb these lists to protect user privacy. So, how are contestants judged in these Olympic Games? Well, there's three criteria. The first scoring criteria is dataset size. So, the more users, the better. The second criteria is accuracy. If you can release a frequency list, that's more accurate, that's better. And the final criteria is privacy. If you're not giving away user passwords, that's also better. So, you may think this is a game that I just made up, but I assure you there's a long history of organizations competing in this event. For example, RockU submitted an entry several years ago with 32 million user passwords. Unfortunately, most of the previous contestants have had to be disqualified due to failure to properly protect user passwords. So, today I want to tell you about a new leading candidate for gold medal. Yahoo just turned in a very strong performance. They collected a dataset of 70 million user passwords, and they used tools from differential privacy to actually perturb these password frequency lists before they were released. So, I should stress that this dataset's available and it was released with permission. So, let's score this entry. First criteria, accuracy. Well, we can actually compare basic statistics like minimum entropy, guessing entropy that you'd get with the sanitized dataset with the same statistics computed on the original dataset. And we actually see that the statistics match in almost every case. With, occasionally, you'll get small variation. And what about privacy? Well, they also had strong scores on the privacy criteria. In particular, they preserved differential privacy with the value, composite value of epsilon equals 0.5. Of course, the single user might participate in multiple different datasets, so you have to scale epsilon appropriately. So, what does this mean? Well, this means we can promise Alice that if we had removed her password from the dataset at the onset, before we ran the differentially private mechanism, the probability of any subset of outcomes doesn't change too much when we exclude her password. So, this means that the probability that Alice gets hacked doesn't change too much, you know, based on whether her password was included or not. Okay, so, password frequency lists have many applications. The simplest one is just, estimate the total number of users that could be compromised in an online attack where the adversary has beta guesses per user. There's lots of other exciting applications. I hope you'll all search for the dataset. If you just search for Yahoo password frequency corpus, you'll find it. Please play around with it. I hope that it's useful for you and for many of you in your research endeavors. And finally, I'd like to conclude by saying that I hope other organizations will challenge Yahoo for gold. There are other organizations that potentially could collect larger password frequency lists and follow the same pattern and perhaps steal that gold medal from Yahoo. So, thank you. Okay, so Nigel's now going to try again with his second presentation. But Kerry, if you're in the room, please get close to the stage because you might be on sooner than expected. Okay, and please take a seat if you're standing in the back corner. I can see you, okay?  Please take a seat, all right? Or leave the auditorium, otherwise we'll get, shut down. This one works. Nigel. Okay, this one appears to work, okay? I don't know, there's something wrong with the computer. We're gonna fix. You'll see the other talk later, I've been promised. Okay, so this is about Speed King. You're gonna hear me sing. So if anyone gets the reference there, if I'm just far too old, really. Okay, okay, except, oh, there we go. Okay, I'm not actually going to sing, right? But if, thank you, thank you for the, that's exactly what I want, yeah, thank you. I'm not gonna sing. But if you're interested in NPC, this is the Rump Session talk for you. So we've got four things to announce. Speed is now open source, and I'm gonna give you the link to that. It will be made open source. It's not actually open source yet, but it will be by the end of the week. There's still some tidying up that they've got to do. Okay, but everything's ready to go.   Do you know where the jobs are? Which university? Bristol, yeah, that's kind of right. There we go. Okay, next one, yeah, right. Okay, so it's now open source. Hopefully now, well, it's gonna be in the next couple of days. The documentation is a little shaky. If you want to sign up for announcements and to find out all about it, there's a Google group called speeds at googlegroups.com, and you can visit the webpage, which is really long, just type Bristol speeds, and you'll get it into Google. Other search engines are available for Brian. You can use Bing if you want, but Google will do it for you. So that's when you can see me fly. If you're gonna have a party, then you need large numbers of people to come to that party. So we decided we wanted a very large party, so we actually ran, well, Marcel did, he ran a 100-party auction. So this is not sugar beet because they only had three parties in their auction, and it was only semi-honest when they did it. This is a proper auction with 100 people, fully malicious, and we actually ran. So when people talk about multi-party computation, the record now is running a computation on 100 parties. We hope to be able to push it to 1,000 parties at some point in the next few months. So the goal is now not to make things faster, but to have more people at your party. And we can now do 22,000, 22,000, 20,000, sorry, blocks per second of AS. This is not as good as Yehuda's record, which is going to be presented at CCS, where he could do a million blocks of AS per second, and he's integrated it into a Kerberos system. But this is a system that will work for many parties, whereas Yehuda's thing only works for three. There we go, so we've got some new kind of cool stuff coming up there. And there's a new workshop. It's going to be, if you go to the website, wwwmultipartycomputation.com, you know, why else would you choose a different URL from that? It's a bit like real-world crypto, which you should have already heard about, okay? It's a bit like that thing, in that there's invited talks. There's a contributed talks call that was announced today on the IECR website, and it's going to be held from April 3rd to April 7th in Bristol. It kind of continues on from the event that used to be held every two years in our hoose, but now we're going to hold it every year and we're going to move around Europe, probably. Oh, I should say that all of my slides have a sort of rowing epitaph, you see, to them, because we're Great Britain, well, we are currently. Um... LAUGHTER And we only excel at Olympic sports where we can apply our Formula One technology. So we're good at cycling, which you would have seen in the real-world crypto talk, but we're also good at rowing as well, because we could just apply technology to it. Doesn't have to be any good at athletics. So that's why we've got the rowing metaphor in all my slides, you see, because we're very good at that. And of course, rowing's quite good for multi-party computation because you need many people to do a good rowing team. You know, it's amazing. Every year we have this Oxen and Cambridge Boat Race. I'm not quite sure how both of them always get into the final, but there we go. But there's eight in each team. Um... Yeah. And so we... So when you need a team of people to do rowing, you need extra people on your team. And so what I want to say in my last slide is, I've just got paid. Shed loads of cash, right? And so with this shed loads of cash, I want to make a better, bigger rowing team. So if you want to join our rowing team, come and help us spend the money. Talk to some of the postdocs who are here. They will tell you, travel is no objective. And come and work for us. Five years, apply online now. Just come and do it. Thank you. Thank you, Nigel. So if you'd like to be a galley slave in Bristol for five years... Hey, hey, hey, hey, hey, yeah. We also have postdocs at Roll Holloway. Please come talk to me. And I'd like now to introduce Kerry McKay or McKay. Good Scottish name there from NIST. Thank you, Kerry. And next up, Marcel. Kerry McKay from NIST, you may have never seen me before because I generally don't like to give these talks, but here I am. So I want to talk to you tonight a little bit about lightweight cryptography and our standardization plans. So you may have heard of us, and we have these standards like AES, SHA-2, SHA-3, but what we're hearing from people is that AES is just too damn tall for the uneven bars. We need something a little bit lighter. So NIST initiated a lightweight crypto project to understand kind of where our standards fall short. So some of you might have come to our first lightweight crypto workshop in July of last year at NIST, and we're gonna hold the second one this October. And what we're looking for is lightweight algorithms for constrained environments and, of course, use cases. So how are we gonna do this is the big question. It's something we've been struggling with. We did just last week put out our draft report, NIST IR 8114, and it's posted for public comment. So after you've had a few drinks, go and look at it tonight. It gives an overview of the project, includes our plan for standardization, which boils down to two essential things. We're gonna recommend primitives based on the application and device profiles, and we're gonna create a portfolio of the lightweight primitives through an open process similar to our 838 series for the modes of operation. And the reason that we're doing this is because if we try and do a competition for this, by the time we finish with the standardization, no one's gonna be using that technology anymore. So the profiles are really the key to what we have. Or the key to our plan. So we're gonna have profiles that represent classes of devices and applications, and we're gonna build these profiles based on public feedback. So this is just a template from the report. If you want more information about what actually goes in these fields, please look at the report. But in general, we've got a primitive, the physical performance and security characteristics, and also some design goals. But here's the thing. We work at NIST, and we're not actually out in the field using this stuff, but you guys are. So we really need your help in developing these profiles. So we have a list of questions in the draft report that we need your input on. We need your answers.  We'll try our best to make up something useful, but you actually know what you need, not us. So right now we've got the draft report out. The comments are due by October 31st. And if you are going to be awesome enough to help us out by answering these questions, to help us develop profiles, it would be really great if you could get those to us by October 1st so that we actually have time to draft some profiles to discuss at the workshop, which again is being held in October 17th or 18th, again at NIST. And if you wanna participate in that, the deadline for submissions is September 9th. So if you would like to contact us or get more information or join our mailing list, we have a lightweight email list like the hash form. There hasn't been much activity on it yet, but hopefully that'll change soon now that the project is picking up. We also have information on the workshop and the project in general. Thank you. Excellent, thank you very much. I've been asked to speak up. Can you hear me at the back okay? Is it good? Yes, excellent. Thank you for one thumbs up at the back. Martyn would like a cup of tea. So if somebody could go fetch Martyn a cup of tea, that'd be great. And if someone could bring me a bottle of vodka, that would be good too, okay? Okay, and that's to prepare us for Marcel Keller, who's next up. And he's gonna be followed by Johan Damon. So if Johan Damon could come to the stage. Thanks Johan, hi Johan. Okay, Marcel. Thank you. So I'm Marcel, I'm one of the slaves. So come talk to me. Please! What I'm gonna talk about today is homopathic encryption. And I have to say it's essentially a shameless deal by a work-in-progress talk from Useniks. I think it was Eric Wustrow. I hope I don't mis-attribute this. So yeah, come talk to me if that's wrong. Anyway, homopathic encryption. Of course, it's gonna be round-based because that's how proper encryption schemes work. We start unsurprisingly with a message M and a key K. And there we go. First round with probability 2 to the minus 12.8, we're gonna assign K to K, otherwise K is XOR, K, XOR, K. We continue with round two. Again, with probability 2 to the minus 12.8, K is equal K, otherwise K equal K, XOR, K. And this already brings us to round number three. Which says that with probability 2 to the minus 12.8, K is K, otherwise K is K, XOR, K. And oh, that's already round number four, with probability 2 to the minus 12.8, K equals K. Otherwise we assign K to K, XOR, K. And now you might be surprised. That's round number five. Probability 2 minus 12.8, K equals K, otherwise K equals K, XOR, K. And let's quickly move to round number six. Probability 2 to the minus 12.8, we assign K to K. Otherwise, that's with probability one minus two to the 12.8, we assign K, XOR, K to K. And then there's my lucky number, round number seven. Probability 2 to the minus 12.8, K equals K, otherwise K, K, XOR, K. Yes, oh yeah, that's one more. That's now round number eight. Probability, so we flip a very heavily biased coin, essentially in all those rounds, 12.2, probably, oh man. Probability 2 to the minus 12.8, we assign K to K, otherwise K is gonna be K, XOR, K, K, K. Oh yeah, that's round number nine. Yeah, I think we have to go to 10, 12, 14, AS style. Two to the minus 12.8, we assign K to K, otherwise K, XOR, K, K, K. 10, oh yeah, that's one more.  Two to the minus 12.8, K equals K, otherwise K equals K, XOR, K. And oh yeah, finalize, cybertext is gonna be C equals M, XOR, K. So that's the scheme. Let's talk about implementation. So we, as you might have seen, that we heavily rely on fast random number generation. And of course, like I know there are chess people here, so you're really concerned about, you know, embedded systems, hardware, maybe there's no fast random number generation. I can assure you I don't have time for this, but there's a slight tweak to the algorithm that makes this algorithm much more efficient on restricted systems. And last but not least, also very important, the design encourages constant time implementation. So if you do if statements on either the message or the key, like you're really doing it wrong. Last but not least, there's also special properties. So we had a thought about this and we're really sure about the fact that quantum attacks are really no better than classical attacks on this one. So that's like for the post quantum probably community. And on the other hand, like for the fancy pants community, of course it's also fully homomorphic. And now here's a nugget for the more, I would say like policy oriented community. We think we strongly believe that this one is particularly suitable for compliance and marketing because it's encrypted after all, right? And this already concludes my talk. Thank you very much. Thanks Marcel, hilarious as ever. And next up, we have a talk called Kangaroo 12 by Johan Daemon and if Brian would like to come to the stage, that would be great. Johan, take it away. Yeah, good evening. This is a more serious talk, I'm afraid. It's a joint work with the Ketchak team and Ronnie, so I call it Ronnie. I choose a sport, so it's a kangaroo. What does a kangaroo do? The boxes, but I don't know if it's an Olympic discipline. Maybe it has been. Haven't seen any boxing, but okay. Our kangaroo boxes and I think you will need it. So what is this basically hashing based on Ketchak P a bit like Châtrier, a bit like the shake functions, but then more efficient. So what we did is we did the exercise to bring Ketchak more down to where it should be to, if you look at the safety margin and we also tried to exploit parallelism. So first, the safety margin. So if you look at the state of crypt analysis, up to now, the best attack, the best collision attack against Ketchak is five rounds. And the best published, there may be some distinguishing stuff, but the best attack is five rounds. But it has 24 rounds. So we basically have more than four and four, a factor of four more rounds than we really need. So in Keeak, we already took that into account and we reduced the number of rounds to half to 12. So let's do also the hashing with 12 rounds. So we reduced from 24 rounds to 12 rounds and that still gives us a factor of two safety margin. So then if we look at modern CPUs, we see more and more these same D instructions going broader and broader. So we have a lot of parallelism that we can do and there's also many CPUs with many cores and we would like to exploit that parallelism. But then in points, basically it's a serial mode. So we introduce a kind of three hash structure and that's basically what we did. So this is the structure of a kangaroo 12. So these blue blocks, they are basically the input blocks of the message. So we split our message into 8192 byte blocks and we can do them in parallel. So you see there those vertical bars that are all inputs to Ketchak. So to a Ketchak version with 12 rounds and we can do them in parallel. And then we append the chaining values to the first block, this S0 and that's also one call. So each of these arrows represents a call to the underlying hash function which is Ketchak with 12 rounds and the whole thing is a three hash mode. So you see also there these chaining values that's some more hashing you have to do but it's compensated by the parallelism. So if you look at these symbols 110 and so on that's in fact padding and frame bits that complies to the Sakura mode. So if you do it this way you get a provable reduction of security to the security of the underlying hash function. So what does this give us? Something went wrong with the slide but okay. Yeah there was a kangaroo there. So on the Haswell and Skylake for short messages you reach about something below around four and between four and five cycles provide but for long inputs you can really exploit this parallelism. So for instance for the Haswell you get down to 1.44 for Skylake 1.22 cycles provide so there you exploit a four level four wide parallelism and on this new CPU night landing basically you can get down to 0.74 cycles provide. So there we put the paper on ICR and you can find the code that has achieved these results in the Ketchak code package that's made public by show. Thank you that's it. Thank you. Thank you. So I'd just like to emphasize that no kangaroos were harmed in the making of that talk. We just don't like kangaroos. And here comes Brian. Okay I'm back for something special. So for what we're calling the charity auction or a long jump for charity. So for the purposes of this talk I am representing the Great Britain and their team in the long jump. For reasons that'll become apparent in a moment for as long as Great Britain it still exists. Iran thanks me for taking you down a walk on Cinema Lane. I'm now gonna take you a walk down ICR lane. In particular I wanna go back 25 years to Eurocrypt 1991. Who knows where Eurocrypt 1991 was held? Okay Kenny go ahead. Brighton and the United Kingdom my first ever Eurocrypt. It was your first Eurocrypt. It was my first Eurocrypt as well. And it was here at the University of Brighton in the UK and who was the general chair? It was Andy Clark that's right. And what was the Eurocrypt 1991 special beverage that everyone got? Beer. In particular something that looked like this. It was Eurocrypt 91 Celebration Ale. And it was my memory of this beer that Andy did that caused me to think about doing a custom label for something which is why we have a wine bottle here with a nice custom label because I kinda grew up from the beard of a wine. Now I accepted to be general chair two years ago and about six months after that I was cleaning out an old box in the back of my closet that had been there probably since graduate school days that I had moved from a bunch of places to places and I'd never seen the light of day and I found this little cardboard box here from Harvey and Sons. And when I opened it up I found inside one unopened original bottle of Eurocrypt 91 Celebration Ale. Best before end of date July 91, okay? It was in April. So I thought what should we do with this bottle since it's a special occasion and it's 25 years and I thought the thing we should do was to have a charity auction to benefit the National Museum of Computing at Bletchley Park. Now so I am about to auction this off for charity. Open your wallets up. Why National Museum of Computing? Well because Andy's a director and trustee of that and it's his favorite charity, he's trying to bring it back. So I thought a way that we could honor Andy in Eurocrypt 91 was to auction this bottle off. So someone here who bids high enough is going to get to walk home with this bottle tonight or make me drink it if they pay me enough. And I hold my fellow members of the board of directors and they have pledged along with me to match the donation that is made by the winning bid tonight if the clicker will advance. So we will get a 27 time multiplier on whatever this goes for that will all go to charity, okay? With some limits so that people don't get too crazy, okay? So what I would like to do right now is open the bidding for this bottle of beer and since it's 25 years old I thought I'd open the bidding at 25 cents. Does someone offer 25 cents? 10 dollars. Okay, I've got a bid of 10 dollars. I've got a bid back there, how much? 20 dollars, 100 dollars over here. And I'm gonna hold you this, thank you very much. Yeah! Wow, fantastic. All right, I've got a bid of 100 dollars for a Eurocrypt 91 celebration ale. How much? 200 dollars, I've got 200 and back. I will offer, he's bid 200, 250, I've got 250. Do I hear 300 in the back? How about 275? Come on, it's for charity. Two, come on, 275. All right, I've got 250 over here. Anyone else? Come on, somebody wants to go a little bit higher, right? It's for charity. 256, I've got 256, all right, all right. All right, 256, it's 512 to you. Or maybe I'll let you go to 384. 384, I've got 384 over here, fantastic, okay. Tom, 384 back to you. No, you're out, you're tapped out. Too many bids, huh? Okay, I have 384 dollars over here, bid for this bottle. Don't you bid dollars? Good, good, we'll be here all night. 384, anyone else? Anyone want to top it? 400, four and some other weird number added onto it. 512, all right, I'm gonna take that 384 dollar bid and I'm gonna let it go once, twice. Last chance, folks, sold for 384 dollars. I think we have raised well a lot of money tonight for the National Museum of Computing. Please meet me afterwards, we're about to go to the break and we will discuss how to make sure that everybody gets tax deductions appropriately for a donation, okay? Thank you all, again, I believe this is the first break. Yeah, so we'll see you all at 2045 for something special involving vegetables, okay? 2045.


So you get me again for the 16S marketing analysis part of the lecture, and also we'll have a bit of hands-on tutorial after this. And the subsequent modules, too, there will be a bit of a hands-on tutorial, so you can actually try out some of the tools we covered in each of the modules. So the learning objective for this module is to understand and perform marketing-based microbiome analysis. Specifically, we'll focus on 16S, ribosomal RNA, we'll use the marker gene to profile and compare the different microbiomes or different microbiome samples, and we'll look at some of the parameters that may affect your marker gene analysis and explain the advantage in this venture, the marker gene-based microbiome analysis, but you actually get a lot of that also in the subsequent sessions comparing marker gene-based analysis to Shaka menogenomic analysis. So the general process is to extract the DNA from your samples to amplify with targeted primers, and once you get your sequences, filter the errors and build OTUs or build ASVs, and then you can carry out some statistical analysis looking at the diversity of your samples across your samples, and also looking at differential abundance of different features in your samples. And when I say features, roughly, it corresponds to the subpopulations in your samples, so each OTU or each TEXA is considered a feature. Okay, so why do we use ribosomal RNAs? There are several good reasons. One is that it's universally present in all living organisms, allowing you to compare the different communities using a single marker gene. It also plays a critical role in protein translation, and because of this functional constraint, it's relatively conserved and rarely acquired through horizontal gene transfer, so it carries with it phylogenetic signals, allowing you to reliably relate organisms with each other. It also behaves like a molecular clock in that it has a relatively stable rate of mutation, so again, useful for phylogenetic analysis and being used to build tree of lives relating all organisms to each other. And 16S, due to its size, has been the most commonly used. So we use RNA as a proxy to understand the microbiome community. So it's a tool that allows you to place organisms on phylogenetic tree and to understand the compositions of the microbial community. So we'll look at how to do that in using China 2 later today. It's also a tool to allow you to compare one community to another, and this is referred to as the beta diversity. And in Rob's lecture, you also see how to relate the different microbial features to the different characteristics that you're interested in, such as obesity versus lean populations, certain disease states such as IBD versus no IBD, and differentially abundant features that are, well, differentially proportioned features that are associated with the properties that you're interested in. Your 16S is not the only marker gene used, and depending on the organisms that you're interested in, there are different marker genes available. For eukaryotes, the commonly used is actually ITS and ATS. Reasons people using these different marker genes is that there have been databases established for these different marker genes, allowing you to compare your data to reference databases. And for bacteria, some of the other ones used include CPN60, which evolves faster than 16S or provides a better resolution than 16S for closely related organisms. Some of the other genes proposed at RECAE, for example, that are single copy genes that allow you to not have to deal with the copy number issues that are present with markers such as ribosomal RNAs. There are multiple copies in the genome. And for viruses, there's no real universal marker genes, but different types of viruses have different markers available to them as sort of communities establish a standard of single conserved genes for a given type of viruses. So for example, G23 has been used for bacterial phage comparison, and RDRP, RNA-dependent polymerase has been used for different RNA viruses. And this publication here has quite an extensive list of marker genes that have been used by researchers for different organism types. So a few considerations for selecting the appropriate marker genes. First is that it should have sufficient resolution to differentiate the different subpopulations of organisms that you're interested in. If you're studying, say, different strains of a given bacterium in a single host, for example, then choosing 16S would not give you the right resolution to be able to come up with strain level differentiation, and you might need much fast evolving markers to do so. So in the case where you're interested in the taxonomic information of the organisms, then the reference database of known species or known organisms is needed for taxonomic assignment. So available of a good reference database for the samples that you're interested in would be necessary in that case. In single copy genes, as I mentioned, it's preferred, but it's not always possible. And certainly for historic reasons, ribosomal RNAs, which is not single copy, have been used as the most common markers for microbiome studies. So when compared across studies, you'll need to use a standardized marker, such as 16S. But more importantly, if you're just sequencing a subregion of 16S using a short read platform such as MySeq, then the different variable regions can also give you different resolutions. So you need to use consistently the same region when you're comparing across data sets. And as Pauline has mentioned, experimental protocols could also affect your results significantly. And mentioned earlier, the different bounds of my pipelines can also affect your results and the importance of keeping track of what you did. So these couple of slides, I had it in here for historic reasons as a reminder, because there's a lot of people asking these questions about DNA extractions and about contamination. So that's why we had a separate lecture today to cover some of these topics in more depth. But here I just listed some of the references on DNA issues with DNA extraction. So one that has been pointed out is that it's possible to carry out some sort of fractionation to separate out different organisms based on cell size or other characteristics. And it's also possible to select for certain fragment sizes based on some automated gel extraction process. So if you're interested in that, there's a video journal about that topic. And just to reiterate that contamination, control for contamination is a major issue in microbiome studies where you don't really know the composition of the microbial community. So as Paul mentioned, that there are different controls that need to be used throughout your experiments. And also when it comes to embryo based studies, sometimes if your target is really low, you can get some non-specific implications, you can get primer-dimers and so on. So when you have low yield or low input volume for your target DNA, then you need to be especially careful regarding the control used to verify that your observation is real. So this is a sort of typical anatomy of a target amplification process. Essentially, let's say you're interested in the V4 region, hypervariable region 4 of your 16S ribosomal RNA. Typically you would design a primer that, of course, a PCR primer that anneals to the conserved regions, flanking the region that you're interested in, but a nifty way of doing a single-step PCR instead of multiple-step PCR is that you can actually attach the sequencing adapters, in this case the Lumina P5 and P7 sequencing adapters to your PCR primer so you can amplify and sequence the target without having to do a two-step PCR amplification. And in addition to that, given the throughput of modern sequencers, we will typically multiplex multiple samples in one single run, so there's a barcode index that uniquely identify each of the samples and typically that's also incorporated as part of your primer design. And there are now many, this is sort of the reference design that was published quite a few years ago by Rob Knight's group and Illumina adopted it, but nowadays there are actually quite a few different amplification protocols available. Okay, so I think I mentioned, most of these already, that in your PCR primer design process, you need to be careful of inhibitors in your samples that may prohibit the PCR process, so adding some internal positive control to make sure the PCR process worked, it's important. And in some complex samples, you could end up amplifying non-target DNA, so downstream in your bioinformatic analysis, it's useful to identify, to make sure that you're indeed amplify the right targets. And sometimes you might want to run your samples on a tape station or on a gel to verify what you have. Okay, so I mentioned there are different variable regions in 16S, ribosomal RNAs. For historically, V4 was chosen because it's the right size for Illumina pair and sequencing. At that time it was 150 base pair, but now it's 250 base pair, so the target has been extended to usually cover V3 and V4 region. And again, STIC was the same protocol that you're using for your entire study, it's important. And as you can see in this little graph here, the different variable regions have different level of conservation, so this Y axis shows the average proportion of the most dominant base, so the lower the peak, the less conserved the particular V region is. And you can see V4, it's actually not the most diverse region, typically speaking. So this paper, this some study looking at the different variable regions and noted that the different variable regions actually selectively pull out, highlight different fractions of your microbial community, different sort of sub-populations of your microbial community. So for example, V1 and V3 favors pervetella and elicit organism here that actually whereas V4 and V6, for example, would selectively pull out a slightly different set of organisms such as campylobacter and enterococcus, which are more gut-associated organisms and so on. And also maybe worth mentioning is that certain bacteria that I also found in the graph, for example, fusobacterium can be missed if you if because the some of the primers use for these regions, even though they're supposed to be universal, still have biases, so they might under-emphasize certain populations of bacteria. Okay, so a current myseq run roughly gets you about 25 million pair m reads, 25 to 30 million pair m reads. And depending on your study design and the diversity of your microbial population that you're interested in and the differences between the different sample types and essentially the effect size that you're interested in, you would need to design your experiment to sample to different depth. And in but in most cases, if you're talking about very diverse communities, a few hundred to a few thousand reads is sufficient to differentiate the community. But if you're looking for some rare biomarkers, or if you're looking for looking for differentials between very similar communities, then you will need to sequence to much deeper coverage. So, but in most cases, I think the recommendation right now is for marker gene analysis is still about 10,000 reads or so, or 10 to 1000 to 100,000 reads or so, should give you enough of a coverage to characterize your popular your microbial population. And if you're sequencing much deeper than that, if the return diminishes, sort of the cost effectiveness, cost effectiveness diminishes. So, as a result of that, you can, you can, you will use unique barcodes to differentiate your samples. And the other issue associated with sample multiplexing or sequencing on MySeq in general is that because the way that the image or the signals is processed on MySeq, when you have very similar sequences, it creates difficulties for the machine to process the image. In other words, you can imagine that all the, so you can imagine that basically the image, I either, if a given base is all the same in your sample, what happens is that the image, because it's taking a shot of the, the different, of the given base that lights up during a given cycle, so your image gets either very bright or very dark depending on the cycle. In other words, the retail synchronized. Then in that situation, what typically you need to do is, you need to do is introduce some diversity in your sequencing pool by adding either some reference sequences to, such as FIX or in your, in your sequence pool to diversify the sequences. Or alternatively, you can sequence different marker genes in a single, single sequencing run to diversify your, your sequence pool. And, okay, so as I mentioned, the convenience of one-step amplification followed by sequencing, sometimes a lot, often, because you're often processing large number of samples, doing a survey using marker gene-based approach, the convenience of one-step amplification is significant over the two-step approach. However, the two-step approach is to allow you to, to attach the same, the same sequencing adopters to different populations of, of marker genes, so different types of marker genes. So, the, so using this protocol, for example, you can mix 16S with 18S with other types of marker genes and, and do a, and, and look at the different fractions of your microbial population. So, for example, in, when we're doing a study looking at what kind of microorganisms, including viruses in water samples, we typically use the two-step amplification process to first use targeted primers to amplify the marker genes, and then anneal the same sequencing adopters to all the different markers and sequencing them all in one go. And this is, as I mentioned, has the added advantage of diversifying your sequencing population, sequencing pool population, and, and therefore improve the quality of the sequencing process. Okay, so now moving into the, the, the different sequencing analysis platforms that we can use for marker gene analysis. The, in this workshop we'll mainly be using CHIME 2, which is sort of a re-re-development or refactoring of the very popular software called CHIME. So how many of you have used CHIME 1 or 2 before? Okay, so about half. How many have used CHIME 2? Okay, so, so for, so for, I'll get into that a bit later. So, so CHIME 2 provides a nice sort of cohesive platform to, to run your analysis in and we'll show, we'll see that in the demo session. But there are also scripts that you can download and run, and one of the popular ones is from Morgan's group called Michael Beimhelper, and I guess, Gavin, are you currently the maintainer for that? Sorry? Yeah, okay, so, so this is sort of a set of scripts that you can download and use to process your marker genes. And there's a third one that was popular, but I mean it's still being used, but it's less popular these days. It's called MOTHER. So how many of you have used MOTHER to analyze your, so, okay, so same people. So I guess you guys try both MOTHER and CHIME. Which one do you prefer? CHIME? Okay, yeah, so MOTHER was, was, was, was very popular before, but because it, CHIME, the first version of CHIME was really quite difficult to use, and it's essentially a collection of scripts that you have to run, and sometimes they don't really have the entire workflow nicely connected, whereas MOTHER provides a uniform platform and uniform ways of entering commands too, and so it's much easier to learn and much easier to use, but it has full out of favor a little bit because, actually the next slide would talk a little bit about that, but also you can build your own custom workflow by combining our scripts, command line scripts, and other tools by coupling, by coupling together different pieces of tools and build your own workflow. So how many of you have done that building your own workflow for marketing analysis? Just one or two? Okay, so, okay, so that's good to know that hopefully the tutorial session will be, will be useful to, to many of you. All right, so I want to do a bit of a comparison between CHIME and MOTHER, just as I say MOTHER, it's, let's use these days for, and for several reasons. One is that CHIME2 has vastly improved its user interface. It's still command line based, but the, the commands are now standardized, and it also, as you'll see later, that it can help you keep track of the steps that you, you do in, in CHIME2. MOTHER has always done that for you in a sort of a log file, keep track of the steps for you, so some people find that nice to be able to know, you know, each steps of your, of your analysis. The key difference between CHIME approach and MOTHER approach is that CHIME has always exists more as a wrapper to, to tools, and so it takes existing tools and then design and, and sort of add it as a plug-in to the CHIME environment, whereas MOTHER typically re-implement popular algorithms and, and have, and as a result of that was able to provide a more sort of cohesive user experience. And both CHIME2 and MOTHER now are very easy to install, typically involves downloading the files and, and run the single command to install it on your, on your system. And in, in the case of CHIME2, it can, it will pull the, the necessary files and all the dependent programs for you automatically in its installation script, so vast improvement over the previous version of, of CHIME. The one downside of CHIME2, however, is that it's a re-implementation, a rewrite of CHIME, of the original CHIME and therefore it has, it still missed quite a few functions available in the original CHIME, but, but hasn't been ported over to CHIME2. Some of those might be sort of historically used, but not no longer relevant, but others such as visualization of phylogenetic trees and so on would be nice to have it natively incorporated in CHIME2 as well, but that's not the case at the moment, so you need external viewers to, to view some of your results. And the other key differences is that for whatever reason MOTHER hasn't implement this ASV-based approach, and I'll talk about the differences between ASV and OTUs shortly, but, and ASV has been proposed as a more accurate way of denoising your samples and identifying subpopulations in your sample. Does anyone know why MOTHER didn't choose not to incorporate any ASV-based approach? I haven't been able to find reasons for that, it's just seem, okay, yeah, because I've found a few sort of blog posts or, or rents in general by, what's his name, Pat, yeah, that sort of still defending OTU with that type of approach, but for whatever reason it hasn't, it hasn't implemented ASV-based approach. Yeah, right, so, yeah, so, so, I mean, most of you heard of OTU before and, and for her story's reasons were still covered in this workshop, but also introducing a new concept called amplicon sequence variant as a new approach to identifying features in your samples. So this is the general bound for MAC workflow that we will go through today in the workshop. So typically you start with one or more FASQ files, in the, in some cases they're still multiplex, in other cases they've been demotiplexed. So there are different scripts or different process that will allow you to take either multiplex samples, demotiplex it first and then, and then run it through the workflow here, or if your samples already demotiplex, then they allow you to associate the metadata to each of the demotiplex samples and then again carry it through the workflow. And as I mentioned, the metadata need to be present in, as part of your analysis and there are tools that will help you manage your metadata and make sure that it's in a standardized format that's acceptable to, to chime. Okay, so the first step is typically to remove the primers and, and of adapters that are found in your sequences. If that hasn't been done for you already, a lot of sequencing centers will give you demotiplexed data back rather than the raw data back and in that, in that, in that case, often the, the adopter and primers are removed. So when you get your data back from a sequencing center, best to check with them what they've done with your sequences before, before deciding what to do for your, by yourself. Okay, so the preprocessing, remove the primers, demotiplex and also look at the sequence quality and remove any reads out of low sequence quality. And also as an option, you can look for ways of, of checking to make sure that your samples consist of only the targets and not other non-specific amplifications. So it could be a decontamination step for your, in the preprocessing. And once you're, once you finish the preprocessing, the next step is called feature identification. This is where you would either combine all your duplicated reads or combining your reads into OTUs based on some predefined cut-offs such as 97% or use this ASV approach. Essentially what you're trying to do is to define the sub-populations in your microbial community and each sub-population is called a feature in your analysis. And then once you have the, the features, you can carry out taxonomic assignments to each of the features by comparing to reference genomes based on sequence similarity, then assign taxonomic name to the, the sequences, to your sequences. And then you, in the same step, you can build your feature table, which I'll explain what that looks like. And the feature table can contain both named and unnamed features that, that you want to care, you want to process and look for differential abundance and so on downstream. Alternatively, you can take those sequences and you can do phylogenetic analysis on the sequence and build phylogenetic tree. But in order to do that first, you need to align your sequences so the, so the, so you, so you can generate the distance matrix for building your phylogenetic tree. And both feature tables and phylogenetic trees then can be used as input for some downstream analysis. Okay, so we'll look at each of these steps a little bit more closely. So for the pre-processing, as mentioned already, the MySeq allow you to multiplex multiple samples in a single run. So the reads from each samples need to be linked back to its, its, to the sample. And this is done using unique barcodes that the, sorry, that the multiplexing step often also remove the barcodes and the primer sequences in, in trying to have several different scripts to help you do that. And this is outlined in the importing tutorial. And I should also mention that mother and other two will also have equivalent demultiplexing algorithms that would, that will work on your sample. Now about the quality filtering. So once you demultiplex your samples, some of the reads will be of lower quality and chime actually filter the reads based on some quality parameters. And this is very similar. So chime two and one had very similar parameters, but it took me a while actually to, to, to identify how the, the statement about how chime two filters by default. So essentially, if you look at the from your, from the three-parmen for a low quality and look at the number of consecutive low quality bases and if it's greater than three, it would start truncating your, your reads from the three-parmen based on the, the number of low quality bases. And the minimum freight quality score required is four to, to be considered sufficient quality. And also if the truncation goes too far far into your read, in other words, more than 70, more than 25% of your reads truncated, then it would drop that entire read. And because some of the downstream denoising steps does not tolerate ambiguous spaces. So by default, chime two would also filter out any reads that has any ambiguous spaces. In other words, ends in, in the sequences. So this is sort of the default filtering parameter in, in chime two, but there are other quality filtering tools available. And, and often in the sequencing center instead of running chime two, they will actually use some of these standalone tools to identify, to identify the, the adapters and, and the primers and remove them. And, and also would trim, in some cases, trim low quality read for you. So again, important to find out your, from your sequencing provider, what they did to the sequences, if they did not give you the, the, the original multiplex fast queue file. And you can, there's a tool called fast QC that's useful to summarize your sequence quality. And we'll see a representation of that in the tutorial session. Okay. So, so I mentioned some of the target amplifier might be non, non, some of the implication might be non specific off target. So you might want to take a subteler sequences and search against 16S or whatever reference databases you have to make sure that it's, it's on target. And also, there are ways to look for host specific contaminations. For example, by searching against host, the human databases, if you have a human sample, just to verify that your reads did not come from the host. Some of the tools, especially classifiers, machine learning based classifiers will happily take any random sequences and spit out some prediction for you. So if you give it a non 16S sequences, if these classifiers might not tell you that it's not 16S, so it will happily make a prediction for you. And so it's, it's, if you're not sure that you indeed have 16S, all your sequences are on target, then it's best to do some spot checking to make sure. Do you have an answer or? So maybe I'll jump to a, pick the diagram. Do I have a, actually it's in my other slide deck. So in Chime, what you can do is actually visualize the, the average quality per base position. So it basically, visually, you can see where the, the quality drop off is. In Chime will allow you to specify you want to cut off that position, and you can do it for both five prime and three prime. So it's sort of visually, visualization of the quality and visually decide what to cut off. And I don't know if it has implementation of, of other tools that would do the sliding window approach to cut it off. I didn't see it when, yeah. So the old version does, but then I don't think the new version the Chime 2 hasn't had that implemented. I guess it's just relying on the visual. So using print seek or other cut adopt or trimmer matics all have similar functions to allow you to trim back the low quality ends. That's right. Yeah. So, yeah. So some of them would allow you to specify, I mean all of them would trim for you, but the sliding window calculation, you say it's in the print seek, right? Yeah. Yes. Yeah. So, so you have ways of specifying which features or which read you want to remove from further analysis. Yeah. Okay. So just to, to reiterate the goal of micro gene analysis is that we're using these marker genes as proxies for the microbial community profiling to understand who's there and understand to, to know the relative abundance of these subpopulations. So we want to be able to divide or partition the community into subpopulations based on their sequence variations. And as I mentioned OT use, use a hard cut off of fixed percentage, typically 97% identity. But to do this, well, the goal found from my analysis is to distinguish true variants from artificial variants that, that are due to PCI amplification or sequencing errors. In other words, try to reconstitute what's in your samples, regardless of the PCR and sequencing errors. And using a hard cut off such as the OT approach, simply doesn't, it's not very accurate. So if we can reconstitute the, the subpopulations, then we can under, we can have a better chance of understanding the subpopulations biological roles and functional roles in the, in the community. And it's also maybe important to, to stress that the traditional OT approach is assuming that every sequence is or in that OTU is treated the same. So just like we say, okay, a given species, if, or given strains of bacteria, you know that it's a population of bacteria, but you, when you give it a label, you essentially treat that whole population the same. So, so the assumption of OTU is that all individuals in an OTU has the same role or function in the community. And certainly, when you do any downstream statistical analysis, you're treating each OTU as the minimum unit of, of analysis. Right. So, so the, as I mentioned already, the OTU picking based on an arbitrary sequence identity. And 97% has been shown to roughly correspond to the species level. But I think I have, but it's actually known that people have done studies looking at reference genomes that the, the percent identity ranges somewhere between one to five or six percent for a given named species. And also the different copies of RNAs in a given genome can have up to one to two percent of variation as well. So making this, this approach not, not very, not very accurate. Okay. So, CHIME supports three different OTU picking algorithms. And this is the original, original CHIME. The new CHIME does do that, but it's actually moved away from OTU picking and looking at the ASV, which I will talk about next. And the three different approaches are the NOVO clustering, close reference and open reference. So, sorry, go ahead. Yeah. So the OTUs are cluster at 99% sequence identity. Yeah. So, I think based on my experience so far, as you think the, the OTU based approach, really, you have to understand your, your organ, your sort of microbial community to pick the right cutoff. So the ASV based approach, which doesn't pre-specify a cutoff, gives you a, I think give you a more accurate representation of, of your microbial community. But yeah. But when you say 99%, so by the way, the slides I have here, slide update from what you might have. So I have to give you the new slides. We'll upload it later this afternoon. Okay. Okay. So for the NOVO clustering, what you're doing essentially is taking all the reads and comparing all other reads and, and create a pair-wise comparison table. And based on the percent identity between the, the two reads, you start grouping them typically using a hierarchical approach. So what that means is that you take the first 99% identical set two sequences, group them together, and then find the next 99% identical sequences to, to this, to the average of this group. And if the next sequence falls outside of the 99% cutoff or the 97% cutoff, then you create a new OTU, a new group. And then you find, again, sequences that are within the cutoff to, to that, what's called a seed sequence in that OTU. So this approach, because you're doing pair-wise comparison to, to set up your, your analysis, it requires a lot of disk and memory space. People have come up with ways of subdividing your, your reads to smaller groups and then only do comparisons within that group. So one, one approach, for example, is that you can first do a, a texanomic analysis of your samples. And then based on high-level texanomic information, such as at the family level, or at the even genus, I think it's those days, at the family or level, you can subgroup your, your reads into different families. And then within that family, build your OTU's within the families to reduce the number of sequences you have to do pair-wise comparison. And there's some studies done to figure out what type of distance measure within a cluster is the most robust. And according to Pash law, who's the developer mother, he found that the average linkage cluster is most robust when you change the input data with the algorithms. But again, as I said, the OTU approach is generally sort of falling out of, out of favor now. Okay, so this is the clustering approach. So as I described, the greedy algorithm is used to achieve time and space saving. So this is achieved by clustering incrementally use, by clustering incrementally using a subset of sequences as centroys. So as I described, when you first encounter a sequence that's, that fall outside of existing OTU's, you make that the new centroid, and then you identify other sequences that are similar to that first sequence that you encountered. But because you're taking the first sequence you encounter as a centroid, what effectively happens is that if you permutate or change the orders of your sequences, then the different centroid will be picked the next time you do the analysis. So as a result of that, you can actually create unstable clusters just by changing the orders of your sequences. So that's one key sort of disadvantage of this greedy algorithm-based approach to clustering. And there are some existing tools that try to get around these issues by first saw your, for example, first saw your sequences from the longest to the shortest, or you favor the longest sequence as the centroid, and so on. So different heuristics to improve the stability of your clustering. In contrast to the novel clustering approach, the close reference essentially is to match your sequence to an existing database of reference sequences. So it's very much a way of assigning taxonomic information to your sequences. The downside of this approach is that if your sequence is not found in the database, then it's discarded rather than used for downstream analysis. So this is quite fast because you're just comparing your list of sequences to reference database. And also you could do this by subdividing your input sequences and parallelize the process, running on different computers. Each subset of your sequences can be run on a different node in a cluster because the determination of the mapping of your sequence to a reference read does not depend on other sequences in your data set. So each can be determined independently. So this is suitable if the samples that you're studying has a really good reference database. In other words, it's a well-studied sample type. So for example, the human microbiome has done a lot of reference genome sequencing. So it has a pretty good set of reference sequences available for comparison. Contrasting that to any of the environmental or animal studies, you have much less information available about the genomes that are found in your samples and certainly much less reference genome sequences available. So close reference is generally good for well-studied sample types but not very good for novel sample types. So this approach called open reference combines essentially the the the novel OTU calling and with the taxonomic mapping approach and give you an OTU table that consists of both the unnamed and the named taxa in the analysis. So because your OTUs actually represent a collection of sequences and when you're doing analysis you cannot take a collection of sequences and analyze it individually. So the next step is how you need to choose one sequence in each of the cluster each of the OTUs as the representative sequence. So you can use that sequence to generate a phylogenetic tree for example or you can use that sequence to calculate a distance matrix. And because you're picking a single representative sequence for a collection of sequences or a collection of organisms essentially it's the downstream analysis is treating all organisms in one OTU the same and so you reduce the a group of organisms down to a single representative sequence and the number of equivalent sequences in that OTU. And the representative sequences can be picked based on some predefined criteria. Often it's the most abundant sequences that are found in a single OTU or the longest sequences that are found in an OTU and sometimes people use the sequence that's at the center of the OTU as the representative sequence. But again like how you pick representative sequence can affect your downstream analysis. And because of this problem a couple years ago new types of denoising what new types of identifying features have been introduced and this is called the ampercon sequence variant. And this is a attempt to avoid an arbitrary dissimilarity threshold and the goal here is to be able to distinguish sequence variants from artifacts that are introduced during sequencing and in much more limited extent during the PCR process. But the biggest disadvantage of this approach is that it's not very it's not sensitive to early round PCR artifacts. So imagine if you have a PCR if you have an early round PCR error that's propagated in your PCR process and it generates multiple copies of itself then this particular algorithm is not able to differentiate that from a true variant data in your sample. So data 2 is one of the approach it stands for division ampercon denoising algorithm. So conceptually how it works is that imagine this is your starting material has these four different species the what let's call it four different texas and the size represent the abundance of each texon. And in the amplification process you might introduce some minor variations due to sequencing errors. So for example these rare ones are derivative of this original population and as a result of that you get these red small dots around it same thing for the green same thing for the the blue and so on. The OTU approach essentially you are drawing fixed radius circles around these in an attempt to essentially hide the artifacts that are derived from sequencing errors in our PCR errors. What data 2 attempts to do is to statistically and using customized error profiles essentially recombine these minor populations due to sequencing errors back to its original population. So re-establish the re-establish the original population structure. So this is one of the supplemental figures from the paper and essentially it's a little bit harder to see here but essentially it's comparing the ASB approach to the OTU approach and on the y-axis it shows the frequency of basically the relative abundance of a feature and the y-axis shows the distance or the variations or the diversity across these features. And the important and this is a mock community so the original population structure is no in what you're seeing here for the for the blue symbols are features that are generated by data to compare to the OTU approach. So what you see here is for features that are both abundant and less abundant but are more similar to each other or more in other words more closely related taxa data 2 is able to differentiate them better than the OTU based approach. And in terms of accuracy because the target population is known you can also see that the the square ones are the what's in the in the mock community you can see that the data to approach reconstitute what's in the mock community better than the OTU based approach. So these square boxes on this side and and also the triangles are considered the the correct ones basically whereas the cross and the stars are considered incorrect and you can see that it does have some some errors in reconstitution that reconstituting the population but generally performs better than the OTU based approach. Now so the even though ASV has been and there are publications recommending the use of ASVs over OTU this block note from here I'll pull it up actually this block note actually discuss what are the the some of the advantages and disadvantages of ASV versus so we actually have a nice description on why the oh sorry there you go has a nice description on why the the ASV approach the pro and cons of the ASV approach but to summarize it as I show you that it the the main improvement is that for organisms that are closely related to each other in your community the ASV approach has better taxonomic resolution in separating them out into subpopulations in your in your sample rather than lumping them together into a single OTU. The other key advantage is that unlike OTUs where you have one representative sequence representing a collection of slightly variable sequences right up to three percent different well up to one percent depending on your cut off the ASV approach provides a consistent label because the algorithm essentially regenerates the the original population structure so each ASV is supposed to represent a cluster of identical sequences so essentially you will get one sequence rather than multiple sequence in each of the cluster and as I mentioned sometimes if you're you have PC early wrong PCR errors then the ASV could actually represent a artifact in your in your experiment but generally speaking it it does pretty good in pretty does a pretty good job in in reconstitution in reconstituting the the populations now the disadvantage is that because it doesn't have that clustering step if your samples are highly diverse if your sample population is highly diverse then or complex then you can have a lot of ASVs and that make the downstream analysis more maybe not more difficult but certainly more more time consuming and and may require more computational resources to do and it's also sensitive to data quality as I mentioned lastly for 16s and other multi-copy genes because each ASV is supposed to represent the cluster of identical sequence so if you have a genome with multiple 16s that are slightly different from each other each of those would become an ASV rather than in the OTU based approach they would be grouped into a single OTU if you use a low enough threshold where the the intracromosome variations does not is not an issue okay so the other feature identification post-processing is the removal of chimera sequences and I won't get into too much detail here but the general principle is you want to look at your reads and identify sequences where the reads map to two different targets in the database two different reference sequences in the database and then that typically signals that you have a chimeric reads so as you can see here the one part of the one part of your query sequence matched the a sequence very well and the second half of your query sequence the one in the middle matched be very well and there are tools that help you pull out those cases as potential chimeric sequences and study shown that approximately one percent of the reads in in a marker gene study can be due to chimeric okay so so taxonomic assignments I mentioned is analogous to close reference genome and close OTU calling I mean so I'm not sure why it's keep jumping so the the process of of of taxonomic assignment is simply to give OTUs a name that you can refer to and the process typically is take the OTUs and the represented sequence from the OTU do some similarity sequence search against a reference database and then take the the top hit or the top several hits as potential candidates for your taxonomic assignment but what's important is to specify the matching algorithms I use and the taxonomic database I use as this could also affect your taxonomic assignment so here's just a list of common databases that's been used for tax taxonomic assignment and here I mentioned that the reason that people use 97 percent is based on the observation that the assumption that the bacterial genera has the species level variation is somewhere between 95 to 99 percent but what's been shown is that actually there are a lot of exceptions to the rule yeah so I've seen it I think charm 2 still uses a version of that but maybe just for archiving purpose and it's not been updated yeah but not okay so but yeah it's good to know that it's not been updated I guess and um yeah so Selva I think is still the one that's been maintained as far as I know but RDP also don't think it's been actively maintained I don't know do you guys have any okay should be okay yeah okay so um as I said green green jeans for historic reasons still had as a archival copy in chime in but um but yeah but it's not been been actively maintained for RDP yeah because I last looked at it it also hasn't had a lot of action so yeah so so I should also mention that NCBI has taken over the some row of curating 16s sequence so NCBI actually does have a 16s database that contains as well all right so so this is just to show that once you have the taxon information you can a common display is to show it in a stack bar chart to show the relative proportions of the different taxon within across different samples or across different sample types okay and I just want to quickly mention the structure of a feature table typically a feature table consists of a sort of the number of the recount of each feature in in a given sample so it's a two-byte it's a two-dimensional table a matrix of features in one direction and and samples in in another direction so each feature could be a an OTU so or an ASV and this represent the number of reads that within that feature from sample one and sample two for example same feature has half the number and as we'll talk about later that typically you need to transform the recount to proportions or to other or normalize some other ways before you do analysis because you sequence first of all you sequence the different samples to different depth so you have different reads per sample and also the read depth is not it the there's correlations of features with each other and that count-based approach to to analyze the the sample would will have unacceptable false discovery rates and biases and the the read table usually is kept in this biome format which i won't we don't need to to get into but it's just to say that there are standardized formats for for different for different for for the microbiome data okay so also for historic context because we have a traditional multiple alignment approach to generate alignment is too slow when you're dealing with tens of thousands sometimes millions of sequences there have been development of template-based aligners one of them is called pine ass and another called inferno based on actually RNA secondary structure for aligning your sequences and these template-based aligner essentially only require your query sequence to align to to the template rather than a pairwise alignment that need to be done in multiple alignment so they're much faster than multiple alignment but they're also less accurate and and generate distance uh less representative of the true phylogenetic distance so the multiple alignment algorithms have been improved to allow at least 10 to thousands of reads to be aligned and this is currently sort of the preferred approach to when you want to generate sequence alignments and then the next step is to generate phylogenetic trees from your sequence alignments again different tree-rich reconstruction tools are available the most popular one is probably the fast tree algorithm that's implemented in charm 2 and and mother and many other tools because large number of sequences to be constructed large number of alignments reconstructed into a phylogenetic tree relatively quickly and relatively accurately uh Rob are you covering rare fraction okay okay okay well I don't think I'll you are so so um as I mentioned because your each of your samples could have different number of reads um and the number of reads can affect the your downstream analysis when you're trying to determine the diversity of your samples and so on so typically if you sequence more uh you get the higher diversity you get higher uh diversity readout so the rare fraction rare fraction process essentially take the same number of reads from each of your samples and um and uh the and and normalize your samples to the same number same number of reads um and this approach has been discussed extensively in the community both the pro and cons and some people say it has minor effect on your on your results some people think it it actually makes it it reduce the sensitivity of your analysis significantly and so on so I highlighted some alternative approaches and and why the field has moved to more compositional based approach rather than count based approach that Rob would mention some of the compositional based approach in this lecture right so um I'll take a few minutes just to finish the last few slides um introducing a few more concepts and then we'll jump into the hands-on portion of the the market gene analysis okay so so we talked about generating a feature table um and using the feature table you can characterize your samples or you can compare your samples to to each other um so I want to introduce a couple concept one is called the alpha diversity analysis and this is the diversity of organisms in a single sample or in a single environment in sort of more traditional ecological study and it's typically a combination of two different measures uh in different ways one is the richness or the number of species where texas are observed or estimated and the second evenness in other words the relative abundance of each texas and you can imagine that's um for the same richness say you have 10 species in the two environments if in one um environment the evenness is is um different such that there's one organism that's highly abundant and the rest are low abundance versus um the second population where it's a second environment where the sub-populations are quite even in other words you have 10 um 10 species that are all roughly the same number if you go into that community that's by by sampling it or by sequencing it the results that you get can be quite different in the first one where you have a highly abundant organism followed by low abundant organisms highly uneven environment you'll have to sequence a lot deeper in order to see the rare um organisms um whereas in this the second one because they're all relatively the same um evenness you'll be able to detect them with much shallower sampling so the alpha diversity can can affect the level of sampling that you require to to see to characterize your um your population so alpha diversity take both evenness and richness into account and there are many many different measures of alpha diversity some common ones such as Shannon entropy uh phylogelastic distance um have been um incorporate into uh chime and into mother and often they do give you um similar um characterization of your community now so um this is just a graph showing if you know if you plot each of your samples in this case two uh samples uh plot their um um alpha diversity in this case the phylogelastic distance in a close reference so the the y-axis is slightly different you can see that in uh for the same set of samples um sequencing to roughly the same depth of coverage when you have close ref using close reference otu pick give you a lower um diversity in this case 20 compared to both open reference and de novo which roughly the same about 30 um uh in the in the um the pd measure so um just to show that the again the otu picking process could affect your diversity measures beta diversity on the other hand uh is the the differences in diversity or plot samples or how different your samples are from um sample types are from each other or different samples are from each other and again there are several um measures of beta diversity one of the popular one is called unifract um and another one uh implemented and in uh chime is its breaker this disability measure uh looking at uh otu abundance across different samples as a measurement of uh of the differences between these samples and contrasting that with the jacar measure the jacar measure only look at otu presence or absence so it does not take abundance into account and so when you are trying to characterize your samples it's also useful to know whether your similarity measures or the similarity measures look uh takes into the relative abundance into account or just measuring the presence or absence of otu's uh or um and uh the the different measures as i mentioned often if your signal is strong enough to give you comparable results but but do have their own caveats that uh that's worth looking into when you're doing comparison when you're picking which ones to use and often by searching for um different discussion forums that people will comment on the on the application of a given diversity to their samples and what they see as the issues associated with the measurements now so so how is beta diversity calculated so when you so instead of the the feature table where you have otu by sample this is actually a table of sample by sample distance measure so so you have to um you have the sample one compared to itself um is um i you know it's it's it's uh obviously identical so you get an assignment for one and um sample one compared to sample two for example less similar so you get a 0.4 in the uh score and the lower the the similarity or the more the dissimilarity the the lower the score and then the but this information does not um you can you can use this to to observe the pairwise distance but um the uh component the um dimension reduction uh algorithm such as principal components or principal coordinate measures allow you to take this and reduce into a two or three dimensional graph so you can more in in a way intuitively see how the the different samples are grouping with each other and and see their similarity and dissimilarity um let me see if i can get to so this is an example of the the principal coordinates graph um taking the distance measure and projecting it onto in this case a two-dimensional graph and intuitively you can see this population here uh it's much more different from this population from these two populations and the these dimensional reduction algorithm works by essentially taking a high dimensional so i have a a graphic picture representation here right so it takes a two-dimension multi-dimensional graph in this case three-dimension and reduce a two-dimension but intuitively you can see that these two representations of of these two different projections one gives you much more information and you can tell that this is a chair whereas this one the way it's projected it gives you a shape that that it's harder to interpret whether it's a chair or if it's something else so the way the these dimensional reduction program works is try to preserve as much information as possible in the high dimension while projecting it in the in the lower dimension so you can visualize it and um commonly it do so by maximizing the variations um in your in your variables okay so um you can also um take all your samples and use the distance measure to build a hierarchical tree and then the uh in in in a way view the clustering as a as a sample tree and samples that are shared um not more similar to each other would be would be would show up show up as clusters in in the tree but this is forced you to show the samples in bifurcation trees so sometimes it could be misleading to to force your samples into bifurcation trees i think i can skip this because i i'm pretty sure i saw some slides talking about the uh the marker gene versus shotgun comparison um so i want to end with um two two fairly new references both published this year um just on gen general um best practice for for um 16 s microbiome studies and and one for this first one actually pretty much covers all the topics we're covering in in this workshop but hopefully the workshop provides you with with sort of a opportunity to to ask some questions related to to these best practices so if you have a chance take a look of these and we can certainly make them available to you if you couldn't download it uh yourself all right you i mean it's not you don't have access through your institutions and whatnot okay so um typically for these labs and certainly in the subsequent sessions we will give you a web link to a version of the um to the lab to the to the lab with instructions and so on but when i was preparing this marker gene lab i was looking at the different um tutorials available online and realize that you know there are some great tutorials out there and it's not really useful for me to reproduce what they do so instead what i want to do is sort of offer you um three different options um one is to but all three options give you an opportunity to use chime 2 to to process some data sets so the first option is just to follow the default the first chime to uh tutorial and this is for beginners who have never used chime 2 before and just want to do the step by step tutorial um and you can also try the second tutorial the the fecal transplant tutorial um which gives you a different starting point uh where the samples have been demotiplaxed already and you take the the demotiplax samples and put in try to and try to import it into chime 2 for analysis uh whereas the first one uh you take a single fast cue uh file that has not been demotiplaxed and then have chime 2 demotiplaxed and do all the processing for you um the second option is uh to use a book chapter that Rob and his student Michael wrote on 16 s analysis so by and large follows the same uh tutorial as the chime tutorial but use a different data set and uh highlights do you have the printout okay great so uh we'll give you the book chapter that you can can take a look um and i'll show you um how to start with the analysis shortly the third option is for for experts basically if you have run chime 2 before where if you have done other analysis before and you have your own data set that you want to just put it through these work uh these workflows you're welcome to try that and then we can try to help you as much as we can in terms of if you have issues or if it gives you an error that you don't know how to fix so um the third option is only for people who have have already used chime 2 uh in the past i should also mention that um the second option we will use the same data set for for module 7 so in a way you we module 7 will give you the results but you this give you an opportunity to play around with the data set and generate the the results that will be used for statistical analysis in module 7