Algorithms in Nature 02317, Spring 2016Course Project Reguarding poster printing: SCS Computing Facilities has instituted a new procedure for printing posters. The new procedure is intended to make the process of poster printing faster and easier for the SCS community. There will no longer be a need to call Operations in order to print a poster. You can now submit posters via email, to poster@cs.cmu.edu. Simply follow the printing procedures that are documented on the SCS Help pages at: http://www.cs.cmu.edu/~help/printing/platinum_printing.html and Operations will print the poster and notify you when it is ready for pickup. Please contact SCS Operations at x8-2608 or send mail to help+@cs.cmu.edu with any questions or concerns. Also, the poster boards we use are 32"x 40" Non SCS students will need to contact their departments about resources for printing posters. -Ziv Your class project is an opportunity for you to explore an interesting algorithmic problem in biology of your choice. Projects can be done by you as an individual, or in teams of two students. Your project will be worth 40% of your final class grade and will have two final deliverables:
In addition, you must turn in a project proposal (1-2 pages) by 03/16.
You must email Ziv (cc Matt) a brief project proposal (1-2 pages maximum) by November 1st. You are encouraged to come up a topic directly related to your own current research project, but the proposed work must be new and should not be copied from your previous published or unpublished work. You may use the list of papers on the Algorithms in Nature website, or the list of topics discussed in class. If you decide to go this route we expect that you either test a new / revised model or idea regarding the paper or apply it to a different dataset then the one discussed in the paper. Simply repeating what was done in the paper is not enough for a class project. Of course you can also choose to work on a new problem beyond our list. Project proposal format: Include the following information:
Project suggestions: Some project ideas are below (more to come later!). We will talk about them in more detail in class. You can also come up with your own project. Projects based on papers from the Biological Distributed Algorithms (BDA) workshops In the past three years we have organized a series of workshops which focus on the same topics as this class. The workshops included state of the art presentations on topics that are very relevant for the class and papers / abstracts presented in these workshops can serve as a good foundation for a project (and also for the class presentation). See links below.
Workshop URLS 2013 BDA workshop. 2014 BDA workshop. 2015 BDA workshop. Project A: Designing robust networks tailored to specific environmental conditions. As we discussed in class, networks need to remain as connected as possible while also deal with cascading failures and attacks. A clique would be highly efficient when no attacks are present, but would immediately fail if any node were attacked and if the errors propagated. A very sparse network would also likely become disconnected if attacked. This project attempts to find the `sweet spot' in connectivity.
References: Prakash B, Chakrabarti D, Faloutsos M, Valler N, Faloutsos C (2011). Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks. (IEEE Computer Society, Washington, DC, USA), pp 537–546. Song J, Singh M (2013). From hub proteins to hub modules: the relationship between essentiality and centrality in the yeast interactome at different scales of organization. PLoS Comput. Biol. 9:e1002910. Project B: Comparing the design of modules within biological networks to modules within the Linux kernel. As we showed in class, modules within biological networks are specifically according to the noise they are expected to face.In the linux kernel, modules depend on other modules and form a call graph. If bugs or errors are introduced in some modules, these errors may propagate and cause failure of the system. This project attempts to find similarities in differences in the way biological networks and operating systems are designed handle errors. References: K-K. Yan et al. Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks. PNAS 107:9186-91, 2010. M. Fortuna et al. Evolution of a modular software network. PNAS 108:19985-9, 2011. Project C: Spider web network design. In order to serve as effective traps, orb webs must intercept prey with a thread, absorb the momentum of the prey (stop it), and retain the prey until the spider can arrive to attack. To perform these functions, orb-web spiders use two primary types of silk threads: (1) sticky threads that are woven in spirals and are used to capture and retain prey; (2) non-sticky threads that are woven radially from the web center and transmit vibrations to the spider. The spider can tug on a radial thread to increase its tension, which allows for more efficient detection of the captured prey. This project investigates how spider strategies and spider webs are designed for various different purposes. References: William G Eberhard. Effects of orb-web geometry on prey interception and retention. Spiders: webs, behavior, and evolution, pages 70–100, 1986. A. T. Sensenig, K. A. Lorentz, S. P. Kelly, and T. A. Blackledge. Spider orb webs rely on radial threads to absorb prey kinetic energy. J R Soc Interface, 9(73):1880–1891, Aug 2012. Kensuke Nakata. Spatial learning affects thread tension control in orb-web spiders. Biology Letters, 9(4), 2013. Many models of distributed computing within computer science make assumptions that appear unlikely to hold within biological systems (e.g. large message sizes that can be passed from one entity to another). New models are being proposed to tighten this link between distributed computing and biology. This is a more open-ended project that can consider theoretical issues in these models, or some implementation using this model to solve a relevant computationa/biological problem. References:Y. Emek et al. Stone Age Distributed Computing. PODC 2012. Y. Benenson et al. Programmable and autonomous computing machine made of biomolecules. Nature 414, 430-434 (22 November 2001. |