String algorithms are everywhere. They underlie both things that you use every day and some exciting cutting edge research. One of the research areas that makes heavy use of string algorithms is Bioinformatics. It studies DNA and genes of humans, animals, and primitive organisms. Genes determine how the organism will develop and which genetic diseases are likely to happen. DNA is a complex three dimensional structure and you can see an example of part of it on the left. You see that it consists of two intertwined strands. We can extract many of the properties of the DNA, if we take just one of those strands and record the sequence of the molecules in it. If we consider just a few dozen types of those molecules called amino acids, and we denote each of them by a Latin letter, then we can convert a strand into a string of Latin letters. And what we can do next is to study those strings. For example, we can put together a string for a human DNA, and for a chimp DNA, and then for a mouse DNA. And then we can find the parts which are the same and the parts which differ. And, this way, we can observe how did the life on earth evolve and what changed in the genes. Another thing we can do with this, is to put a genome of a person with a rare genetic disease next to a genome of a healthy person. Find the differences and then make hypotheses on which mutations in the genes cause these genetic disease which can help to later cure it. You will hear more about it later in the course from Pavel Pevzner who has been working in the field of Bioinformatics for decades. Moving on to everyday things, depending on where you are now, you probably use one of these search engines every day: Google in most of the world, Yandex in Russia, Baidu in China, or Naver in South Korea. Search engines crawl the Internet and download petabytes of data that they find there. And, then, when you type in your search query they use mostly the text of those documents in the Internet to match to your query. And those texts can represent the strings, lots of string algorithms are used in the process. Another example is your favorite text editor when you launch spellchecking or are just trying to find something in your text, string algorithms are working. A less obvious example is the software which protects our computers and computer networks. The anti-virus software looks for suspicious patterns in the code of the programs that you want to launch on your computer and the network intrusion systems looks for suspicious patterns in the network traffic. So, a string algorithms are a great tool for pattern matching both exact and approximate string algorithms are used in the software. Last, but not least, software engineers are needed to implement all of the stuff that I've shown to you and they need their own tools. If you've ever participated in a programming project within a team, then you've probably reviewed some changes made by one of your teammates. And you use some version control system and a diff tool built in into the system, like the one in the example with Wikipedia. And to guess correctly what was changed in the code or in the Wikipedia article without actually knowing what was changed, string algorithms are used for aligning and matching parts of the text. In this course, we will start with applications of string algorithms to Bioinformatics. You will hear about that from Pavel Pevzner who also has a whole separate specialisation in Coursera about Bioinformatics. You will see how basic string algorithms can be applied to solve the problems which are raised in Bioinformatics. And, then, the second part of the course you will meet again with me and we will work through some algorithmic challenges around how to make those algorithms to run really fast. And fast enough, for example, to apply them to genomes which consist of millions or even billions of characters, or to the text in the Internet, in your text editor, and so on. Also, in the end of the specialization, you will have a capstone project called Genome assembly. And, there, you will apply string algorithms, graph algorithms, and other algorithms to build the genome from a million pieces. See you later in this course.
