1
$\begingroup$

I will soon have around 8 weeks to do a research project of my choosing as I am finishing my undergrad in computer science. My experience is mostly in optimisation algorithms (mostly combinatorial/discrete optimisation).

I have an interest in applying computer science to biology (mostly human biology). I would like to ask if anyone knows optimisation problems with applications to biology which would benefit current research.

Although I have read a lot about biology in my free time, I am not too knowledgeable about the current state of the research and so it is a bit hard for me to find a good topic.

Some examples to spark the discussion are string problems in genetics (alignment problems), and community detection in graphs (to find proteins in the same functional group).

Thank you!

$\endgroup$
  • 2
    $\begingroup$ Optimization algorithms have lot of scope in computational biology. 'Almost' all parameter fitting requires one or another of such algorithms. I would say look into some computational biology, bioinformatics journals, you will find tons of examples. $\endgroup$ – Dexter Oct 27 '15 at 3:59
  • $\begingroup$ Optimization is ubiquitous in all sciences and engineering, and biology is no exception. Many statistical models in neuroscience require optimization for example (my area). $\endgroup$ – Memming Oct 27 '15 at 13:25
  • $\begingroup$ It is probably worth picking one such algorithm and make an answer out of it. $\endgroup$ – Remi.b Oct 27 '15 at 18:29
  • $\begingroup$ Note that genetic algorithms are a type of optimisation algorithm that is inspired from evolutionary biology. Some people used the knowledge the computer scientist have acquired in studying these algorithms to understand evolutionary biology. For example, questions such as "What fraction of the space of possibilities is explored before reaching an optima?" can be of interest. $\endgroup$ – Remi.b Oct 27 '15 at 18:31
  • $\begingroup$ Depends on your area of expertise --- continuous / local optimization, or discrete, combinatorial problems? There are many discrete problems in next-generation sequencing applications and network (graph) models. Continuous optimization problems frequently arise in various statistical models (maximum likelihood fitting to data). Optimization is a large field, so would be helpful if you can be more specific as to your area of interest. $\endgroup$ – Roland Oct 27 '15 at 22:18
2
$\begingroup$

Maximum likelihood phylogenetic trees. The trees are easily scored but the tree space is so large that finding optimal phylogenetic trees is extremely difficult. There's some research but there haven't been very many actual breakthroughs, so it's probably a pretty rich field.

$\endgroup$
  • $\begingroup$ Well I guess this is a nice example! There's tons of papers on the subject. Here is one and another one. $\endgroup$ – Remi.b Oct 27 '15 at 20:21
1
$\begingroup$

Here are some examples:

  • Sequence (DNA, protein) alignment. With the development of next-generation sequencing methods, this is an important and active field.
  • Genome distance calculation by genome rearrangements
  • The phasing problem for single nucleotide polymorphism data (determining haplotypes)
  • Factor blocking problems in statistical experiment design
  • Network (graph) analysis. Many biological data sets can be expressed as networks, for example pairwise protein interactions, which give rise to a variety of discrete problems, like finding maximum connected subgraphs, graph flow problems, etc.
  • Biclustering of data matrices, notably gene expression data
  • Inference on phylogenetic trees was already mentioned.

I'm sure there are many more, this is just off the top of my head. Happy googling! :)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.