Course: Algorithms for Biological Sequence Analysis
Spring semester, 2011
9:10 - 12:10 Tuesday, 107 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/seq11spr
Instructor: Kun-Mao Chao (趙坤茂)
Teaching assistant: An-Chiang Chu (朱安強)
Prerequisites: Some basic knowledge on algorithm development and program design is required. Background in bioinformatics and computational biology is welcome but not required for taking this course.
Coursework:
Homework assignments and Class participation (10%)
Two midterm exams (70%; 35% each):
1. April 12, 2011 Scoreboard I II by An-Chiang
2. May 24, 2011
Oral presentation of selected papers (20%)
Our classmates: I
II (by An-Chiang)
III [Fire alarm. Run!]
IV [An-Chiang, the Master]
V [Thank you for being the background of this
camera.] (by Kun-Mao)
Class PowerPoint slides:
Introduction [2/22/2011]
Interesting Sequences [2/22/2011]
Basic Algorithmic Strategies [3/1/2011]
Sequence Alignment [3/8/2011][Thank Chih-Hsin for his corrections.]
Space-Saving Strategies [3/15/2011]
Suboptimal Alignments [3/22/2011]
Multiple Sequence Alignment [3/29/2011]
Homology Search Tools [4/19/2011; 4/26/2011]
SNP [4/26/2011; 5/10/2011]
Heaviest Segments [5/10/2011; 20115/17]
RMSQ [2011/5/17]
Supporting materials:
Molecular Biology for Computer
Scientists by
Basic Algorithmic Strategies by Kun-Mao Chao
Global Alignment by Kun-Mao Chao
Local Alignment by Kun-Mao Chao
Various Scoring Schemes by Kun-Mao Chao
Space-Saving Strategies by Kun-Mao Chao
Chao, K. -M., Pearson, W. R. and Miller, W., 1992, Aligning Two Sequences within a Specified Diagonal Band, Computer Applications in the Biosciences (CABIOS, now Bioinformatics), 8: 481-487.
Chao, K.-M., Hardison, R. C. and Miller, W., 1993, Constrained Sequence Alignment, Bulletin of Mathematical Biology, 55: 503-524.
Chao, K. -M., 1994, Computing All Suboptimal Alignments in Linear Space, Combinatorial Pattern Matching '94, Lecture Notes in Computer Science 807, 31-42, California, USA.
Chao, K. -M., Hardison R. C. and Miller, W., 1994, Recent Developments in Linear-Space Alignment Methods: a Survey, Journal of Computational Biology, 1: 271-291.
Chao, K.-M.,
1996, On Building an Interactive Alignment Tool,
International Symposium on Combinatorics and Applications
(SOCA '96), 84-93,
Mainland
Multiple Sequence Alignment by Kun-Mao Chao
Homology Search Tools by Kun-Mao Chao
Huang, Y.-T., Zhang, K., Chen, T. and Chao, K.-M., 2005, “Selecting Additional Tag SNPs for Tolerating Missing Data in Genotyping,” BMC Bioinformatics, 6: 263.
Huang, Y.-T., Chao, K.-M., and Chen, T., 2005, “An Approximation Algorithm for Haplotype Inference by Maximum Parsimony,” Journal of Computational Biology, 12: 1261-1274.
Chang, C.-J., Huang, Y.-T., and Chao, K.-M., 2006, “A Greedier Approach for Finding Tag SNPs,” Bioinformatics, 22: 685-691.
A Note on Computing Heaviest Segments by Kun-Mao Chao
Chen, K.-Y. and Chao, K.-M., 2007, “On the Range Maximum-Sum Segment Query Problem,” Discrete Applied Mathematics, 155: 2043-2052.
Homework assignments:
#1: Handout: Feb.22, 2011; Due: March 4, 2011
Send TA (anchiang [not not at] gmail.com) a PowerPoint page including: (Subject: [HW1] Your student ID number)
Your Name
A sequence which, in your opinion, is sort of interesting or inspiring.
A short reason explaining why it is interesting or inspiring.
More sample solutions: 2007 2008 2009
2011 [3/8/2011]
Class presentations:
1. The expected number of team members: ~ 8;
2. Each member is required to present in turn;
3. Revised slides should be sent to me one week after the presentation; (Please compress your figures.)
4. Questions in class are always welcome.
Selected papers for presentation:
5/31/2011
[1] Paul G. Howard and Jeffrey Scott Vitter "Practical Implementations of Arithmetic Coding" Image and Text Compression, ed. by James A. Storer, Kluwer Academic Publication, 1992. More references: http://www.data-compression.info/Algorithms/AC/index.htm
蔡佩真 楊鈞傑 吳浩庠 李佳憲 李枝新 朱民晃 吳彥緯 姚甯之
黃信博
Slides
[2] Q. Wang, D. Korkin, and Y. Shang, “A Fast Multiple Longest Common Subsequence (MLCS) Algorithm,” IEEE Transactions on Knowledge and Data Engineering (TKDE), vol. 23(3), 2011.
施羽芩 李鴻欣 劉士弘 周緯志 林耿生 江蘇峰 黃安婷 張世杰
潘彥謙
Slides
6/7/2011
[3] Eugene Myers and Webb Miller, "Optimal Alignments in Linear Space," CABIOS (Bioinformatics) 9: 169-176, 1988.
黃博平 陳彥璋 李政緯 涂宗瑋 王柏易 林澤豪 林萬泉
Slides
[4] Chao, K.-M., Hardison, R. C. and Miller, W., 1993, Locating Well-Conserved Regions within a Pairwise Alignment, Computer Applications in the Biosciences (CABIOS, now Bioinformatics), 9: 387-396. (PostScript version)
洪晧瑜 賴宜萍 陳筱雯 魏昭寧 蔡長蓉 吳冠龍 何家全 林琬瑜
Slides
6/14/2011
[5] Jan Fostier, Sebastian Proost, Bart Dhoedt, Yvan Saeys, Piet Demeester, Yves Van de Peer, and Klaas Vandepoele, "A greedy, graph-based algorithm for the alignment of multiple homologous gene lists," Bioinformatics, (2011) 27 (6): 749-756.
林建旻 葉士賢 黃柏翔 翁正勳 凌璟騰 麻立恆 高國書 駱家淮
陳振翔
[6] Quentin D. Atkinson, "Phonemic Diversity Supports a Serial Founder Effect Model of Language Expansion from Africa," Science (15 April 2011): Vol. 332 no. 6027 pp. 346-349.
黃曳弘 程士洵 廖堃吉 林怡萱
