Computational Issues in Molecular BiologyCSE 397 / 497Spring Semester 2004Professor Daniel LoprestiDepartment of Computer Science and EngineeringLehigh University, Bethlehem, PA 18015Email: [email protected] ~ Homepage: http://www.cse.lehigh.edu/~loprestiReading ListTu 1/20 Introduction molecular biology ITh 1/22 No class: Professor Lopresti in California*****Tu 1/27 Introduction to molecular biology II(1) Chapter 1 in Introduction to Computational Molecular Biology, J. Setubal and J.Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “The Blueprint for Life?” by D. G. Feitelson and M. Treinin, IEEE Computer, July2002, pp. 34-40.http://ieeexplore.ieee.org/iel5/2/21883/01016899.pdf?isNumber=21883&prod=JNL&arnumber=1016899&arSt=34&ared=40&arAuthor=Feitelson%2C+G.%3B+Treinin%2C+M . (3) If you don't already know the material: Chapter 2 in Introduction to ComputationalMolecular Biology, J. Setubal and J. Meidanis, Pacific Grove, CA: Brooks/ColePublishing, 1997.=====Th 1/29 Basics of sequence comparison and alignment(1) Section 3.1-3.2 in Introduction to Computational Molecular Biology, J. Setubal andJ. Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “A General Method Applicable to the Search for Similarities in the Amino AcidSequences of Two Proteins” by S. B. Needleman and C. D. Wunsch.not available on WWW – see Blackboard archive(3) “The String-to-String Correction Problem” by R. A. Wagner and M. J. Fischer.http://doi.acm.org/10.1145/321796.321811*****Tu 2/3 Advanced sequence comparison and alignment(1) Section 3.3 in Introduction to Computational Molecular Biology, J. Setubal and J.Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “The emerging landscape of bioinformatics software systems” by L.S. Heath and N.Ramakrishnan, IEEE Computer, July 2002, pp. 41-45.http://ieeexplore.ieee.org/iel5/2/21883/01016900.pdf?isNumber=21883&prod=JNL&arnumber=1016900&arSt=41&ared=45&arAuthor=Heath%2C+L.S.%3B+Ramakrishnan%2C+N=====Th 2/5 Block editing models and algorithms(1) “The String-to-String Correction Problem with Block Moves,” W. F. Tichy, ACMTransactions on Computer Systems, vol. 2, no. 4, November 1984, pp. 309-321.http://doi.acm.org/10.1145/357401.357404(2) “Block Edit Models for Approximate String Matching,” D. Lopresti and A. Tomkins,Theoretical Computer Science, vol. 181, no. 1, 1997, pp. 159-179.http://www.cse.lehigh.edu/~lopresti/Publications/1997/tcs97.pdf*****Tu 2/10 Database search: BLAST, FAST, and GenBank(1) Section 3.5 in Introduction to Computational Molecular Biology, J. Setubal and J.Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “Rapid and Sensitive Protein Similarity Searches,” D. J. Lipman and W. R. Pearson,Science, vol. 227, no. 4693, 1985, pp. 1435-1441.http://links.jstor.org/sici?sici=0036-8075%2819850322%293%3A227%3A4693%3C1435%3ARASPSS%3E2.0.CO%3B2-S(3) “GenBank,” D. A. Benson, I. Karsch-Mizrachi, D. J. Lipman, J. Ostell and D. L.Wheeler, Nucleic Acids Research, 2003, Vol. 31, No. 1, pp. 23-27.http://nar.oupjournals.org/cgi/reprint/31/1/23=====Th 2/12 Cross-domain string matching(1) “Cross-Domain Approximate String Matching,” D. Lopresti and G. Wilfong,Proceedings of the Sixth International Symposium on String Processing andInformation Retrieval, September 1999, Cancún, Mexico, pp. 120-127.http://www.cse.lehigh.edu/~lopresti/Publications/1999/spire99.pdf*****Tu 2/17 Sequence comparison & alignment: Arthur Loder(1) “Alignment of Whole Genomes,” A. L. Delcher, S. Kasif, R. D. Fleischmann, J.Peterson, O. White, and S. L. Salzberg, Nucleic Acids Research, vol. 27, no. 11,1999, pp. 2369-2376 .http://www.tigr.org/software/mummer/MUMmer.pdf(2) “A Space-Economical Suffix Tree Construction Algorithm,” E. M. McCreight,Journal of the ACM, vol. 23, no. 2, April 1976, pp. 262-272.http://doi.acm.org/10.1145/321941.321946=====Th 2/19 Sequence comparison & alignment: Jesse Wolfgang(1) “The Multiple Sequence Alignment Problem in Biology,” H. Carrillo and D. Lipman,SIAM Journal on Applied Mathematics, vol. 48, no. 5, October 1988, pp. 1073-1082.http://links.jstor.org/sici?sici=0036-1399%28198810%2948%3A5%3C1073%3ATMSAPI%3E2.0.CO%3B2-O(2) “Trees, Stars, and Multiple Biological Sequence Alignment,” S. F. Altschul and D. J.Lipman, SIAM Journal on Applied Mathematics, vol. 49, no. 1, February 1989, pp.197-209.http://links.jstor.org/sici?sici=0036-1399%28198902%2949%3A1%3C197%3ATSAMBS%3E2.0.CO%3B2-0*****Tu 2/24 Sequencing and sequence assembly: Lan NieScribe: Shi Chen(1) Section 4.1-4.2 in Introduction to Computational Molecular Biology, J. Setubal andJ. Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “Genome sequence assembly: algorithms and issues,” M. Pop, S.L. Salzberg, and M.Shumway, IEEE Computer, July 2002, pp. 47-54.http://ieeexplore.ieee.org/iel5/2/21883/01016901.pdf?isNumber=21883&prod=JNL&arnumber=1016901&arSt=47&ared=54&arAuthor=Pop%2C+M.%3B+Salzberg%2C+S.L.%3B+Shumway%2C+M.=====Th 2/26 Sequencing and sequence assembly: Upmanyu MisraScribe: Deepthi Bollu(1) Sections 4.3-4.4 in Introduction to Computational Molecular Biology, J. Setubal andJ. Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “The greedy path-merging algorithm for sequence assembly,” D. H. Huson, K.Reinert, E. W. Myers, Proceedings of RECOMB 2001, pp. 157-163.http://doi.acm.org/10.1145/369133.369190*****Tu 3/2 Physical mapping of DNA: Shanna TerryScribe: Jesse Wolfgang(1) Sections 5.1-5.2 in Introduction to Computational Molecular Biology, J. Setubal andJ. Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “The enhanced double digest problem for DNA physical mapping,” M-Y Kao, J.Samet, and W-K Sung, Proceedings of the 7th Scandinavian Workshop on AlgorithmTheory (WAT00), 2000, pages 383-392.http://www.daimi.au.dk/~cstorm/bioinf_f02/project3/kao:sam:sun:2000.pdf=====Th 3/4 Physical mapping of DNA: Shi ChenScribe: Tom Morrisette(1) Sections 5.3-5.4 in Introduction to Computational Molecular Biology, J. Setubal andJ. Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.*****Tu 3/9 Spring break: no classTh 3/11 Spring break: no class*****Tu 3/16 Phylogenetic trees: Benjamin LoyleScribe: Patrick Schmid(1) Section 6.1 in Introduction to Computational Molecular Biology, J. Setubal and J.Meidanis, Pacific Grove, CA: Brooks/Cole Publishing, 1997.(2) “Designing Fast Converging Phylogenetic Methods,” Luay Nakhleh,