VL Algorithmen und Datenstrukturen für Bioinformatik WS2015/2016 Woche 1 (19400001) Tim Conrad AG Medical Bioinformatics Institut für Mathematik & Informatik, Freie Universität Berlin Einige Inhalte basieren auf Folien von Jones&Haake (RIT), Batzoglou (Stanford) Die Themen heute Verwaltung 1. 2. 3. 4. 5. Team Tutorien Praktikum Prüfungsleistungen Vorlesung Introduction Tim Conrad, VL AlDaBi, WS2015/16 2 Das Team • Tim Conrad – BSc/MSc Bioinformatik 2000-2005 – Professor für Medizinische Bioinformatik (seit 12/2014) – Email: [email protected] – Sprechstunde Mo 15-16h, Arnimallee 6, Raum 137 • Thimo Wellner & Kathleen Gallo (VL) – Emails: [email protected], [email protected] • Hannes Hauswedell, Johannes Röhr, Jongkyu Kim (Praktikum) − Emails: { hannes.hauswedell | johannes.roehr | j.kim } @fu-berlin.de Tim Conrad, VL AlDaBi, WS2015/16 3 Tutorien • Termine – Ü1: Di 08:00 (c.t.) – Ü2: Di 12:00 (c.t.) – Ü3: Do 08:00 (c.t.) – Ort: Seminarraum 053 (Takustr. 9) – Beginnt am 20.10.15 • Einteilung − Bitte JETZT in die Listen eintragen. Tim Conrad, VL AlDaBi, WS2015/16 4 Währenddessen… Bitte auf den Kärtchen eintragen: (1) Welche Aminosäuren sind hier abgebildet? (2) Auf welche 2-3 Themen würden Sie in der VL gerne einen Schwerpunkt legen? Ü1: Di 08:00 Ü2: Di 12:00 Ü3: Di 16:00-18:00 Tim Conrad, VL AlDaBi, WS2015/16 5 Auflösung Tim Conrad, VL AlDaBi, WS2015/16 6 Tutorien • Nachbesprechung des VL-Inhaltes • Wöchentliche Kurztests/Reviews – Statt Übungszetteln – 15 Minuten am Anfang des Tutoriums – wer zu spät kommt, kann nicht mehr teilnehmen! – Egal in welchem Tutorium teilgenommen wird – 3 A-Fragen – Verständnisfragen – Müssen schriftlich beantwortet und abgegeben werden – 3 B-Fragen – „Für zu Hause“ – Besprechung im nächsten Tutorium Tim Conrad, VL AlDaBi, WS2015/16 7 Tutorien • Bewertung − Die Fragen werden mit „+“/“0“/“-“ bewertet − „+“ steht dabei für die perfekte Antwort , die der Musterlösung ähnlich ist − Insgesamt 50% der A-Fragen müssen ausreichend korrekt („+“ oder „0“) beantwortet werden • Achtung: BONUS! − Wird eine Antwort mit „+“ bewertet, zählt das einen Bonus-Punkt für die Klausur − Das heißt: in 14 Wochen Tutorium (15. wird „Review“) können bereits 42 Bonus-Punkte für die Klausur erreicht werden − In der Klausur müssen 90 von 150 Punkten erreicht werden Tim Conrad, VL AlDaBi, WS2015/16 8 Praktikum • Findet VL-begleitend statt – Montags, 12-14h – Wöchentlich abwechselnd praktische und theoretische Veranstaltungen – Siehe: www.mi.fu-berlin.de/w/ABI/AlDaBiWS15Praktikum • Aufgaben angelehnt an die „VL Blöcke“ – Praktische Programmier-Aufgaben – 6 Projekte (+1 freiwilliges) • 2er Gruppen – Festzulegen vor der 1. Veranstaltung (per Wiki, s.o.) – Können danach nicht mehr geändert werden Tim Conrad, VL AlDaBi, WS2015/16 9 Praktikum • Ausgabe jeweils zu den praktischen Veranstaltungen • Abgabe nach zwei Wochen – Abzugeben (per SVN) ist der jeweilige Sourcecode – Ein Projekt ist bestanden, wenn 75% der automatisierten Tests funktionieren – Achtung: Code muss auf einem Pool-Rechner compilieren – Hinweise zu Dateinamen und Ein- / Ausgabeformat beachten! Tim Conrad, VL AlDaBi, WS2015/16 10 Praktikum • Die eingereichten Programm werden zwar automatisch getestet und dadurch bewertet, • ABER jedeR TeilnehmerIn kann bei der wöchentlichen „Lotterie“ gezogen werden und muss dann in der Lage sein, die Lösung zu erklären und Fragen zum Quelltext zu beantworten. • Personen können mehrfach dran kommen. • Personen die nie gezogen wurden, können zum Ende des Praktikums "manuell gezogen" werden. Tim Conrad, VL AlDaBi, WS2015/16 11 Prüfungsleistungen – wie bestehe ich? • Wöchentliche Kurztests – 50% der A-Fragen mit „+“ oder „0“ beantwortet • Klausur – 90 von 150 Punkten erreicht (inkl. max. 42 Bonuspunkte) – Ähnliche Fragen wie A und B Fragen aus Tutorium – Vermutlich in der letzten Semesterwoche – Nachklausur vermutlich 2 Wochen später • Praktikum – Fristgerechte Abgabe und korrekte Lösung von 75% der Projekte – Bestandene Lotterie-Interviews • Teilnahme an VL wird empfohlen Tim Conrad, VL AlDaBi, WS2015/16 12 Vorlesung • Vorlesung wird auf deutsch gehalten • Folien sind fast ausschließlich in englisch • Folien werden zeitnah online verfügbar gemacht. Eine Mitschrift des Folieninhaltes ist nicht nötig. • Die Folien sind KEIN Skript. Hinzu kommen Erklärungen, Tafelanschrieb, Beispiele, Hinweise, Anekdoten, Overheadfolien, … Gehen Sie in die Vorlesung und machen Sie sich Notizen. VL Homepage: • http://www.medicalbioinformatics.de/teaching Tim Conrad, VL AlDaBi, WS2015/16 13 Feedback • Antworten auf konkrete Fragen (z.B. Themen, Quiz) • Hinweise zur Vorlesung (z.B. Fehler auf einer Folie) • Konkrete Fragen, die sie über diesen Termin im Kurztest oder der Klausur stellen würden • Gerne anonym Tim Conrad, VL AlDaBi, WS2015/16 14 Soweit zum Administrativen Fragen zur „Verwaltung“? Tim Conrad, VL AlDaBi, WS2015/16 15 Introduction Before we start… Tim Conrad, VL AlDaBi, WS2015/16 16 The Context of Bioalgorithms • It is important to keep in mind that a mathematically perfect solution to an ideally posed problem may not be the most biologically relevant • We need a flexibility, a willingness to rephrase the question, to rethink the process, to adapt and re-adapt Tim Conrad, VL AlDaBi, WS2015/16 17 Expectations – Computing Background • There are skills you should possess in part already, but which will be significantly enhanced by being exercised in this course: • identifying and clearly phrasing a computational problem from a general biological question • locating existing tools • understanding the capabilities and limitations of such tools • rapidly developing, testing and analyzing tools for the solution of such problems if necessary Tim Conrad, VL AlDaBi, WS2015/16 18 Computing Background – Specific skills • Programming in a language such as Lisp, Perl, Scheme, Java, C/C++, Python, etc. • Static and dynamic data structures – arrays, lists, trees, etc. • Programming paradigms, especially recursion • Rapid prototyping, careful version control • Understanding of mathematics for: • analysis • proof • modeling Tim Conrad, VL AlDaBi, WS2015/16 19 Introduction Why are we doing this? Tim Conrad, VL AlDaBi, WS2015/16 20 Biological Motivation • The fundamental building blocks of life are proteins and nucleic acids • 100,000 or so different proteins in a human • Enzymes, structural proteins, transport molecules, antibodies • Their properties and interactions are what make us what we are Tim Conrad, VL AlDaBi, WS2015/16 21 Biological Motivation • Nucleic Acids • DNA and RNA • Encode the information necessary to build proteins • Pass this information on from generation to generation Tim Conrad, VL AlDaBi, WS2015/16 22 Biological Motivation • What are proteins? • Polymers of amino acids (20 different) • Sequence of these amino acids (primary structure) determines the protein’s shape (secondary and tertiary structures) • Protein shape and chemical composition of it’s amino acids determine protein function Tim Conrad, VL AlDaBi, WS2015/16 23 So…in theory, we can infer protein function if we know the protein sequence Figure from W. Gilbert, Ph.D New Hampshire Biotech. Center Tim Conrad, VL AlDaBi, WS2015/16 24 Text comparison? Tim Conrad, VL AlDaBi, WS2015/16 25 Biological Motivation • How do we find out protein sequence so that we can understand structure, function, and ultimately systems biology? • State-of-the-art • Can sequence proteins directly • this has been technically difficult but is getting better • More often we determine protein sequence from the nucleic acid sequences that encode them Tim Conrad, VL AlDaBi, WS2015/16 26 The Central Dogma • Hereditary information for a complete individual stored in the DNA, which is selfreplicating, and is organized into units of expression (genes) • A gene is expressed in 2 steps: • • DNA is transcribed into RNA RNA is translated into protein Tim Conrad, VL AlDaBi, WS2015/16 27 Using DNA Sequence to Discover Protein Information • Why do it? • Availability of DNA sequence information • Rapid development of DNA sequencing technology • Genomes of many different species have now been sequenced • Difficulties? • Data sets are large • Cellular pathway from DNA to RNA to protein can be complicated Tim Conrad, VL AlDaBi, WS2015/16 28 Some Genomes • E. coli • 4.6 x 106 bases Approx. 4,000 genes • Yeast 15 x 106 bases • Approx. 6,000 genes • Smallest human chromosome 50 x 106 bases • Human 3 x 109 bases • Approx. 30,000 genes ? Tim Conrad, VL AlDaBi, WS2015/16 29 The Computational Approach • The nucleotide sequence of a genome contains all information necessary to produce a functional organism • Therefore, we should, in theory, be able to duplicate this decoding using computers • what do you think about this? Tim Conrad, VL AlDaBi, WS2015/16 30 Why Use Computational Techniques? • The datasets are too large to analyze by hand • Efficient algorithms are the only way to perform the analyses that we need to answer the biological questions Tim Conrad, VL AlDaBi, WS2015/16 31 The Biologists View to Sequence Analysis • Many common biological problems can be answered through comparison of DNA sequences Tim Conrad, VL AlDaBi, WS2015/16 32 Some Biological Questions Answered Through Sequence Analysis • Determine if an interesting DNA sequence has been seen by anyone else • Find all the protein coding regions in a genome • Infer the function of a new gene from a known one by matching two amino acid sequences • Measure the evolutionary distance between species • Predict local secondary structure of a peptide sequence, predict protein conformation, predict function • Study protein families Tim Conrad, VL AlDaBi, WS2015/16 33 The Computer Scientists’ View • (Many) Problems on biological sequences are string matching problems • Operations on strings are standard in the CS algorithm toolbox • DNA is a string of A’s, T’s, G’s, C’s Tim Conrad, VL AlDaBi, WS2015/16 34 Computer Scientists vs Biologists Tim Conrad, VL AlDaBi, WS2015/16 Biologists vs computer scientists • (almost) Everything is true or false in computer science • (almost) Nothing is ever true or false in Biology Tim Conrad, VL AlDaBi, WS2015/16 36 Biologists vs computer scientists • Biologists seek to understand the complicated, messy natural world • Computer scientists strive to build their own clean and organized virtual world Tim Conrad, VL AlDaBi, WS2015/16 37 Biologists vs computer scientists • Computer scientists are obsessed with being the first to invent or prove something • Biologists are obsessed with being the first to discover something Tim Conrad, VL AlDaBi, WS2015/16 38 But: both disciplines “need” each other … bioinformatics? Tim Conrad, VL AlDaBi, WS2015/16 What is bioinformatics? National Center for Biotechnology Information (NCBI): [Bioinformatics is] the field of science in which biology, computer science, and information technology merge to form a single discipline. The ultimate goal of the field is to enable the discovery of new biological insights as well as to create a global perspective from which unifying principles in biology can be discerned. Tim Conrad, VL AlDaBi, WS2015/16 40 Biology Molecular Biology Chemistry Medicine Bioinformatics Mathematics Statistics Physics Computer Science Informatics Tim Conrad, VL AlDaBi, WS2015/16 41 Mehr Informationen im Internet unter medicalbioinformatics.de/teaching Tim Conrad AG Medical Bioinformatics www.medicalbioinformatics.de Weitere Fragen
© Copyright 2024 ExpyDoc
