Course: Algorithms for Biological Sequence Analysis
Fall semester, 2009
13:20 - 16:20 Monday, 107 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/seq09fall
Instructor: Kun-Mao Chao (趙坤茂)
Teaching assistant: Yi-Ching Chen (陳怡靜) email: d94010@csie... (TA office hours: TBA)
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 (15%)
Two midterm exams (60%; 30% each):
1. October 26, 2009
2. December 7, 2009
Oral presentation of selected papers (25%)
Class PowerPoint slides:
Introduction [Sept. 14, 2009]
Interesting Sequences [Sept. 14, 2009]
Basic Algorithmic Strategies [Sept. 21]
Sequence Alignment [Sept. 28 & Oct. 5]
Space-Saving Strategies [Oct. 5 & Oct. 12]
Suboptimal Alignments [Oct. 19; Midterm: Oct. 26]
Homology Search Tools [Nov. 2]
Multiple Sequence Alignment
[Nov. 16]
DNA Sequencing and Protein Sequencing [Nov. 9]
SNP [Nov. 23]
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
Homology Search Tools by Kun-Mao Chao
Multiple Sequence Alignment 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: September 14, 2009; Due: September 25, 2009
Send TA a PowerPoint page including: (Subject: [HW1] Your student ID number)
Your Name
A sequence which, in your opinion, is sort of interesting or inspiring, noting if it is your own creation or collection.
A short reason explaining why it is interesting or inspiring.
More sample solutions: 2007 2008
Class presentations:
1. The expected number of team members: ~ 4
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:
2009/12/14
Brookes, A.J., 1999, The
essence of SNPs, Gene, 234(2):177-86.
林志瑋 蕭聖穎 簡廷因 許榮財
2009/12/21
International HapMap Consortium, 2007,
A second generation human
haplotype map of over 3.1 million SNPs, Nature, 449(7164):851-61.
高文洪 黃怡嘉 彭姵晨 傅莉雯
2009/12/28
Teo, Y.Y., et al., 2009,
Singapore Genome Variation Project: a haplotype map of three Southeast Asian
populations, Genome Research, 19(11):2154-62.
曾子豪 朱百一 曾聖耀 高峻偉