everything.study
18.413

Introduction to Computational Molecular Biology

3-0-9 units · Undergraduate

Introduction to computational molecular biology with a focus on the basic computational algorithms used to solve problems in practice. Covers classical techniques in the field for solving problems such as genome sequencing, assembly, and search; detecting genome rearrangements; constructing evolutionary trees; analyzing mass spectrometry data; connecting gene expression to cellular function; and machine learning for drug discovery. Prior knowledge of biology is not required. Particular emphasis on problem solving, collaborative learning, theoretical analysis, and practical implementation of algorithms. Students taking graduate version complete additional and more complex assignments.

Spring 2004 · Error-Correcting Codes Laboratory

Topics

  • Introduction
  • Channels and Capacity
  • Probablities and Decoding Codes
  • Gaussian Channels, Parity Product Code
  • Introduction to Belief Propagation
  • The Markov Property
  • Linear Codes
  • LDPC Codes
  • In-class debugging session
  • Belief Propagation on Trees
  • Representing Probabilities
  • LDPC on Binary Erasure Channels
  • Convolutional Codes
  • Turbo Codes
  • Serial Concatenated Codes
  • Developments in iterative coding
  • Lecture on Developments in Iterative Decoding
  • Lecture on Classical Codes
  • Student Presentations

Readings

  • Fan, John L. Constrained Coding and Soft Iterative Decoding. Kluwer International Series in Engineering and Computer Science. Boston: Kluwer Academic Publishers, 2001. ISBN: 079237455X.
    Listed reading
  • Luby, M. G., M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. “Efficient Erasure Correcting Codes.” IEEE Transactions on Information Theory 47, no. 2 (February 2001): 569-584.
    Listed reading
  • Benedetto, Divsalar, Montorsi, and Pollara. “Serial Concatenation of Interleaved Codes: Performance Analaysis, Design, and Iterative Decoding.” IEEE TIT 44, no. 3 (1998): 909-926.
    Listed reading
  • Brink, Stephan Ten. “Code Characteristic Matching for Iterative Decoding of Serailly Concatenated Codes.” Ann. Des Telecommun 56, no. 7-8 (2001): 394-408.
    Listed reading
  • Davey, Matthew C. “Error-Correction using Low-Density Parity-Check Codes.” Thesis, University of Cambridge, December 1999.
    Listed reading
  • Brink, Stephan Ten. “A Rate One-half Code for Approaching the Shannon Limit by 0.1dB.” IEE Electronics Letters 36, no. 15 (July 2000): 1293-1294.
    Listed reading
  • Davey, Matthew, and David MacKay. “Low-Density Parity Check Codes over GF(q).” IEEE Communications Letters 2, no. 6 (June 1998): 165-167.
    Listed reading
  • Jin, Khandekar, and McEliece. “Irregular Repeat-Accumulate Codes.” Second International Conference on Turbo Codes. September 2000.
    Listed reading
  • Luby, Mitzenmacher, Shokrollahi, and Spielman. “Improved Low-Density Parity-Check Codes Using Irregular Graphs.” IEEE Transactions on Information Theory 47, no. 2 (February 2001): 585-598.
    Listed reading
  • Chung, Richardson, and Urbanke. “Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation.” IEEE TIT 47, no. 2 (2001).
    Listed reading
  • Richardson and Urbanke. “The Capacity of Low-Density Parity-Check Codes Under Massage-Passing Decoding.” IEEE TIT 47, no. 2 (2001).
    Listed reading
  • Richardson, Thomas J., M. Amin Shokrollahi (Member IEEE), and Rüdiger L. Urbanke. “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes.” IEEE Transcattions on Information Theory 47, no. 2 (February 2001): 619.
    Listed reading
  • Shannon, Claude E., and Warren Weaver. Mathematical Theory of Communication. Urbana, Illinois: University of Illinois Press, 1963. ISBN: 0252725484.
    Listed reading
  • Fan, John L. Constrained Coding and Soft Iterative Decoding. Kluwer International Series in Engineering and Computer Science. Boston: Kluwer Academic Publishers, 2001, SECS 627.
    Listed reading

Prerequisites & course information

Subject meets with 18.417 Prereq: 6.1210 or permission of instructor Acad Year 2027-2028: U (Spring) Acad Year 2028-2029: Not offered 3-0-9 units

Sources