Sequence Informatics, Fall 2008, DSU

7714-101 - Sequence Informatics, Fall 2008

"Scholars of the highest class, when they hear about the Tao, take it and practice it earnestly.
Scholars of the middle class, when they hear of it, take it half earnestly.
Scholars of the lowest class, when they hear of it, laugh at it.
If it were not laughed at, it would not be fit to be the Tao."
(Lao Zi, Dao De Jing, chapter 41)

Announcements

Oct. 21 - Please submit the proposal by the end of October!
Oct. 21 - HW3 is posted. Deadline is November 6.
Oct. 9 - We have a class at 9 am tomorrow in the room 702.
Oct. 2 - HW2 is posted. Deadline is October 18.
Sep. 17 - The meeting room is changed to UIT 310.
Sep. 12 - HW1 is posted. Deadline is September 30.
Sep. 12 - Lecture notes of week 2 is posted.
Sep. 4 - The Greatest Beginning!

Course Information

Course Background - We will focus on theories and methods to deal with sequences. Sequences can be observed in all natural phenomena. Sequence is related with a lot of research applications, which include Information Theory, Machine Learning, Bioinformatics, Security Informatics, Time Series Analysis, etc. In those applications, diverse researches are actively performed.
Course Description We will discuss the following items
- String algorithms: Rabin Karp, Finite Automata, Knuth-Morris-Pratt, Suffix Tree
- String alignment: Pairwise sequence alignment, Multiple sequence alignment, Plagiarism detection.
- Machine Learning: Generative Model for Sequences, n-gram Augmented Naive Bayes, Hidden Markov Model, Conditional Random Field, Advanced sequence models.
- Security and Intrusion Detection: Host-based/Network-based Intrusion Detection, User behavior modelling, How to detect SQL Injection Attck?
- Data Mining: Sequential Association Rule Discovery, Frequent Patterns
- Information Theory: Entropy, Kolmogorov Complexity, Model Selection Criteria (Bayesian Information Criteria, Akaike Information Criteria)
- Time Series Analysis: ARIMA Model, ARMA Model, ARMAX Model, State Space Model
Course Objectives - TBA
Course Prerequisites - TBA
Target Audience - TBA
Course Policies - TBA

Course Staff

Instructor - Dae-ki Kang, Ph.D.

Course Schedule

Lectures : Wednesday 2pm-5pm @ U310
Office Hours : by appointment thru e-mail, or Monday 10am-5pm

Texts and References

Texts - The course materials will be composed of the selected texts from the following:
- Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology by Dan Gusfield
- Time Series Analysis and Its Applications: With R Examples by Robert H. Shumway, David S. Stoffer
- [CLRS] Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
- Pattern Recognition and Machine Learning by Christopher M. Bishop
- Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (Old version is available online.)
- Introduction to the Theory of Computation by Michael Sipser
- Computability and Complexity Theory by Steven Homer and Alan L. Selman
- Elements of Information Theory by Thomas M. Cover and Joy A. Thomas
- Data Mining: Concepts and Techniques by Jiawei Han, Micheline Kamber
- Probabilistic Robotics by Sebastian Thrun
Lecture Notes - Week 2 : String matching algorithms (PDF)
Quizes, Homeworks, Tests - TBA

Course Materials

Syllabus
Study Guide
- Week 11
  - A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data by Eleazar Eskin et al.
  - Data mining approaches for intrusion detection by Wenke Lee, and Salvatore J. Stolfo
  - Data Cleaning and Enriched Representations for Anomaly Detection in System Calls (PDF) by Gaurav Tandon, Philip Chan and Debasis Mitra
  - Modeling Multiple Time Series for Anomaly Detection (PDF) by Philip K. Chan and Matthew V. Mahoney
  - On the learning of system call attributes for host-based anomaly detection (PDF) by Gaurav Tandon and Philip K. Chan
  - Trajectory Boundary Modeling of Time Series for Anomaly Detection (PDF) by Matthew V. Mahoney and Philip K. Chan
  - Learning Useful System Call Attributes for Anomaly Detection (PDF) by Gaurav Tandon and Philip K. Chan
  - Dynamic analysis of malicious code (PDF) by Ulrich Bayer et al.
  - Anomalous System Call Detection (PDF) by Darren Mutz, et al.
  - Protecting Users Against Phishing Attacks (PDF) by Engin Kirda, and Christopher Kruegel
  - A multi-model approach to the detection of web-based attacks (PDF) by Christopher Kruegel, Giovanni Vigna, and William Robertson
  - Overbot - A botnet protocol based on Kademlia (PDF) by Guenther Starnberger, Christopher Kruegel, and Engin Kirda
  - Visual-Similarity-Based Phishing Detection (PDF) by Eric Medvet, Engin Kirda, and Christopher Kruegel
  - Saner: Composing Static and Dynamic Analysis to Validate Sanitization in Web Applications (PDF) by Marco Cova et al.
  - Improving Signature Testing Through Dynamic Data Flow Analysis (PDF) by Davide Balzarotti et al.
  - Secure Input for Web Applications (PDF) by Martin Szydlowski et al.
  - Panorama: Capturing System-wide Information Flow for Malware Detection and Analysis (PDF) by Heng Yin et al.
  - Detecting System Emulators (PDF) by Thomas Raffetseder et al.
  - Mining Specifications of Malicious Behavior (PDF) by Mihai Christodorescu
  - A Layout-Similarity-Based Approach for Detecting Phishing Pages (PDF) by Angelo Rosiello
  - On the Effectiveness of Techniques to Detect Phishing Sites (PDF) by Christian Ludl
  - Dynamic Spyware Analysis (PDF) by Manuel Egele et al.
  - Exploring Multiple Execution Paths for Malware Analysis (PDF) by Andreas Moser et al.
  - Cross Site Scripting Prevention with Dynamic Data Tainting and Static Analysis (PDF) by Philipp Vogt et al.
  - Preventing Cross Site Request Forgery Attacks (PDF) by Nenad Jovanovic et al.
  - Behavior-based Spyware Detection (PDF) by Engin Kirda et al.
  - Using Static Program Analysis to Aid Intrusion Detection (PDF) by Manuel Egele et al.
  - SecuBat: A Web Vulnerability Scanner (PDF) by Stefan Kals et al.
  - Pixy: A Static Analysis Tool for Detecting Web Application Vulnerabilities (Short Paper) (PDF) by Nenad Jovanovic et al.
  - TTAnalyze: A Tool for Analyzing Malware (PDF) by Ulrich Bayer et al.
  - Noxes: A Client-Side Solution for Mitigating Cross Site Scripting Attacks (PDF) by Engin Kirda et al.
  - An Anomaly-driven Reverse Proxy for Web Applications (PDF) by Fredrik Valeur et al.
  - Using Generalization and Characterization Techniques in the Anomaly-based Detection of Web Attacks (PDF) by William Robertson et al.
  - Polymorphic Worm Detection Using Structural Information of Executables (PDF) by Christopher Kruegel et al.
  - Automating Mimicry Attacks Using Static Binary Analysis (PDF) by Christopher Kruegel et al.
  - Protecting Users Against Phishing Attacks with AntiPhish (PDF) by Engin Kirda et al.
  - Reverse Engineering of Network Signatures (PDF) by Darren Mutz et al.
  - Detecting Kernel-Level Rootkits Through Binary Analysis (PDF) by Christopher Kruegel et al.
  - Static Disassembly of Obfuscated Binaries (PDF) by Christopher Kruegel et al.
  - Anomaly Detection of Web-based Attacks (PDF) by Christopher Kruegel et al.
  - On the Detection of Anomalous System Call Arguments (PS) by Christopher Kruegel et al.
  - Run-time Detection of Heap-based Overflows (PS) by William Robertson et al.
- Week 10
  - Chapter 2 of Elements of Information Theory by Thomas Cover and Joy Thomas (Entropy, Relative Entropy, and Mutual Information)
  - Kolmogorov Complexity (PDF) by Lance Fortnow
  - Model Selection Criteria for Learning Belief Nets: an Empirical Comparison (PDF) by Tim Van Allen, Russ Greiner
  - Kolmogorov Complexity (PDF) by Neil Conway
  - Quantum Kolmogorov Complexity (PDF) by Andre Berthiaume et al.
  - Transfer Learning using Kolmogorov Complexity: Basic Theory and Empirical Evaluations (PDF) by M. M. Hassan Mahmud and Sylvian R. Ray
  - Project topic : Quantum Computer
    - The Quantum Computer : An Introduction by Jacob West
    - Quantum computer in Wikipedia
    - Shor's algorithm in Wikipedia
    - Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer by Peter W. Shor
    - Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance by Lieven M. K. Vandersypen et al.
    - Implementing Shor's algorithm on Josephson Charge Qubits by Juha J. Vartiainen et al.
    - Implementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit Array by Austin G. Fowler et al.
    - A Refinement of Shor's Algorithm by David McAnally
- Week 9
  - Sets, Functions and Countability by David R. Wilkins
  - THE INTEGERS AND THE REAL NUMBERS
  - Cardinality of Infinite Sets
  - Turing Machines by Jurg Nievergelt
  - Complexity: P and NP by Jurg Nievergelt
  - Godel's Incompleteness Theorem by Dale Myers
- Week 7
  - Chapter 13 of Pattern Recognition and Machine Learning by Christopher Bishop (Sequential Data)
  - Classical Probabilistic Models and Conditional Random Fields (PDF) by Roman Klinger and Katrin Tomanek
  - Project topic : Suffix DAG
    - Augmenting Suffix Trees, with Applications (PDF) by Yossi Matias, et al.
    - Efficient Implementation of Suffix Trees (PDF) by Arne Andersson and Stefan Nilsson
- Week 6
  - Chapter 13 (PDF) of Introduction to Information Retrieval by Christopher D. Manning et al.
  - Chapter 6 of Machine Learning by Tom Mitchell (Bayesian Learning)
  - Machine Learning in Automated Text Categorization (PDF) by FABRIZIO SEBASTIANI
  - Text Categorisation: A Survey (PS) by Kjersti Aas and Line Eikvil
  - Scalable and Accurate Intrusion Detection using n-Gram Augmented Naive Bayes and Suffix Tree by Dae-Ki Kang
  - A Bayesian approach to filtering junk e-mail (PDF) by Mehran Sahami et al.
- Week 5
  - Chapter 11 of Algorithms on Strings, Trees, and Sequences by Dan Gusfield (Core String Edits, Alignments, and Dynamic Programming)
  - Sequence Alignment Lecture Notes #1 (PDF) by Unknown
  - Sequence Alignment Lecture Notes #2 (PDF) by Unknown
  - Pairwise Sequence Alignment (PPT) by Jorng-Tzong Horng
  - Semi-Global Alignment (PDF) by Robert Hochberg
  - Affine Gap Penalty Alignment (PDF) by Robert Hochberg
  - Suffix Tree (PDF) by Robert Hochberg
  - Project topic : Intrusion Detection, Software Fault Detection
    - Intrusion Detection: A Bioinformatics Approach by Scott Coull, et al.
    - SQL Injection Attack Detection: Profiling of Web Application Parameter Using the Sequence Pairwise Alignment by Jae-Chul Park and Bong-Nam Noh
    - Network Anomaly Detection Based on Clustering of Sequence Patterns by Sang-Kyun Noh et al.
    - Detection of Parameter Manipulation Using Global Sequence Alignment by Jae-Chul Park and Bong-Nam Noh
    - Sequence Alignment for Masquerade Detection (PDF) by Scott E. Coull and Boleslaw K. Szymanski
    - Root Cause Analysis Using Sequence Alignment and Latent Semantic Indexing by R. P. Jagadeesh Chandra Bose and U. Suresh
    - Conditional Random Fields for Intrusion Detection (PDF) by Kapil Kumar Gupta et al.
  - Lowest common ancestor
    - Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE (PDF) by Johannes Fischer and Volker Heun
    - Nearest Common Ancestors: A Survey and a New Distributed Algorithm (PS) by Stephen Alstrup et al.
    - The LCA problem revisited (PS) by Michael A. Bender and Martin Farach-Colton
  - Decision Tree Lecture Note by Andrew W. Moore
  - Multiple Sequence Alignment (TBA)
- Week 4
  - Chapter 15 of CLRS (Dynamic Programming)
  - Chapter 16 of CLRS (Greedy Algorithms)
  - Bill Gates' predictions about speech recognition: a historical review by Matthew Paul Thomas
  - Dynamic Programming Lecture Notes #1 (PDF) by Jeff Parker
  - Dynamic Programming Lecture Notes #2 (PDF) by Robert Hochberg
  - Project topic : Plagiarism Detection
    - Plaggie: Plaggie: GNU-licensed Source Code Plagiarism Detection Engine for Java Exercises (PDF) by Aleksi Ahtiainen, et al.
    - XPlag: Plagiarism detection across programming languages by Christian Arwin and S. M. M. Tahaghoghi
    - SID: Shared Information and Program Plagiarism Detection (PDF) by Xin Chen et al.
    - Sim: Sim: a utility for detecting similarity in computer programs by David Gitchell and Nicholas Tran
    - Software for detecting suspected plagiarism: comparing structure and attribute-counting systems (PS) by Kristina L. Verco and Michael J. Wise
    - YAP3: YAP3: Improved detection of similarities in computer program and other texts by Michael J. Wise
    - SNITCH: SNITCH: a software tool for detecting cut and paste plagiarism by Sebastian Niezgoda and Thomas P. Way
    - JPlag: JPlag: Finding plagiarisms among a set of programs by Lutz Prechelt, Guido Malpohl
    - MOSS: Winnowing: Local Algorithms for Document Fingerprinting (PDF) by Saul Schleimer et al.
    - SIM: Detecting copied submissions in computer science workshops (PS) by Dick Grune and Matty Huntjens
  - Huffman Tree Example (PDF) by Lyn Turbak
- Week 3
  - Chapter 6 of Algorithms on Strings, Trees, and Sequences by Dan Gusfield
  - On-line construction of suffix trees (PDF) by Esko Ukkonen
  - Ukkonen's suffix tree algorithm (PDF) by Thomas Mailund
  - Fast String Searching With Suffix Trees by Mark Nelson
  - CANDID: Preventing SQL Injection Attacks using Dynamic Candidate Evaluations (MP4) by Ventkat Venkatakrishnan
  - BibTeX from Wikipedia, the free encyclopedia
  - BibTeX.org
  - JabRef reference manager
- Week 2
  - Lecture notes : String matching algorithms (PDF)
  - Chapter 32 of CLRS (String Matching)
  - Graphviz - graph visualization software
  - FreeMind - free mind mapping software
  - AcroEdit - an advanced free text editor for windows
  - A Fast String Searching Algorithm by R.S. Boyer and J. S. Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772
  - String Searching over Small Alphabets by Matyas Sustik and J. S. Moore. UTCS Tech Report TR-07-62
- Week 1
  - Chapter 2 of CLRS (Growth of Functions)
  - [Web page] Research skills by Simon Peyton Jones
  - [Slides] How to give a good research talk by Simon Peyton Jones
  - [Slides] How to write a great research paper by Simon Peyton Jones
  - The Not So Short Introduction to LATEX2e
  - MiKTeX Project Page
  - TeXnicCenter
  - Ghostscript, Ghostview and GSview
Problem Sets - HW1, HW2, HW3
Lab Assignments - TBA
Term Projects - Proposal deadline is Oct. 30th.
Examinations - TBA
Grades

Last modified: Sep. 4, 2008