====== Classic Papers on Algorithms in Bioinformatics (2S) ======


| ekvv TBA| Bohnenkämper | Summer 2023 | (Monday, 16-18 in U10-146) |


===== Contents =====

The students will read influential research papers on Algorithms in Bioinformatics from earlier periods. The focus this semester is going to be on Comparative Genomics. Each student will select one such paper and give a preferably concise oral presentation (~ 25 min). They will subsequently write a summary of their chosen paper.
Whether the summary passes or not is decided primarily on its clarity and completeness, not its length.

Both the presentation and the summary are requested to be in English as it is the dominant language of the research in this area.

In the initial sessions after the assignment of topics, we will discuss the papers as a group and resolve any questions or difficulties together. Optionally (depending on the experience of the students), we will also cover an aspect of scientific reading and writing in each of these sessions.


----


The class will be held in person in U10-146 as long as the current situation is favorable enough. On student request or resulting from a change in the situation, the class may be transferred to a hybrid or Zoom class.

===== Deadlines =====

  * The written summary is to be handed in **at most two weeks** after the presentation.
  * If you are unsure whether your presentation fits the format, you should make an appointment with me //approximately one week// before the presentation.

===== Schedule =====

| **Date**  | **Topic** | **presented by** |
| <del>03.04.</del> | | |
| <del>10.04.</del> | (Leonard away) | |
| <del>17.04.</del> | (Leonard away) | |
| 24.04. | Organizational Matters/Reading Articles | Leonard |
| <del> 01.05. </del>  | (May day) | |
| 08.05. | Topic Selection/Writing/Talking | Leonard | 
| ... | ... | ... |



=====Suggested Literature=====

===Stringology in Bioinformatics===
  * Altschul et al. 1990: [[https://www.sciencedirect.com/science/article/pii/S0022283605803602 | Basic local alignment search tool (BLAST)]]
  * Manber & Myers 1993 [[https://epubs.siam.org/doi/abs/10.1137/0222058 | Suffix Arrays: A New Method for On-Line String Searches ]]
  * Durbin 2014: [[https://academic.oup.com/bioinformatics/article/30/9/1266/236397 |  Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT)  ]]

===Reversal Model===
  * Sankoff 1992: [[https://link.springer.com/chapter/10.1007/3-540-56024-6_10 | Edit distance for genome comparison based on non-local operations ]]
  * Caprara 1999: [[ https://epubs.siam.org/doi/abs/10.1137/S089548019731994X  | Sorting Permutations by Reversals and Eulerian Cycle Decompositions ]]
  * Bergeron 2001 : [[ https://link.springer.com/chapter/10.1007/3-540-48194-X_9 |  A Very Elementary Presentation of the Hannenhalli-Pevzner Theory ]] 
  * Bergeron & Strasbourg 2001: [[ https://link.springer.com/chapter/10.1007/3-540-44696-6_13 | Experiments in Computing Sequences of Reversals ]]
  * Bader, Moret & Yan 2001 : [[ https://link.springer.com/chapter/10.1007/3-540-44634-6_34 | A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study]]

===DCJ (-Indel) Model===
  * Bergeron, Mixtacki & Stoye 2006 :  [[https://link.springer.com/chapter/10.1007/11851561_16 | A Unifying View of Genome Rearrangements]]
  * Braga, Willing & Stoye 2011 : [[ https://www.liebertpub.com/doi/10.1089/cmb.2011.0118 |  Double Cut and Join with Insertions and Deletions ]]
  * Compeau 2013 : [[ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3655023/ | DCJ-Indel sorting revisited ]]

===Breakpoint and other distances ===
  * Tannier, Zheng & Sankoff 2009: [[https://doi.org/10.1186/1471-2105-10-120 | Multichromosomal median and halving problems under different genomic distances]] (possibly needs to be split)
  * Feijao & Medianis 2011: [[https://ieeexplore.ieee.org/abstract/document/5719602 | SCJ: A Breakpoint-Like Distance that Simplifies Several Rearrangement Problems]]


===Your own ideas?===
You might be inspired by
  * [[teaching:alggrliterature | the Algorithms in Genome Research Literature ]]
  * [[teaching:2021winter:cg |  the Algorithms in Comparative Genomics Literature ]]
  * [[teaching:2023summer:sa| the Sequence Analysis Literature]]
  * reading the references of the papers listed here
  * ...