Мне интересно: какие проблемы в биоинформатике может помочь решить теория графов?

Есть целый ряд проблем, которые теория графов может быть применена:  

Сборка генома. Теория графов используется в разлиных поколениях сборочных программ, в виде графа перекрытия и графа де Брёйна.   

Исследование геномных перестроек. Сортировка самого экономного сценария перестройки генома требует разрешения графа точек остановки.  

Предсказание структуры РНК и белков. Смежность остатков в РНК или белковых структурах может быть описана на графике контактов. Кроме того, декомпозиция графа используется для решения модульных компонентов или мотивов (например, псевдоузел).  

Графическая кластеризация. Это может быть полезно для поиска мотивов в сети белок-белковых взаимодействий или семейств белков на графике сходства последовательностей. Некоторые инструменты (например, MCL) могут генерировать мотивы или кластеры, моделируя потоки внутри сети.  

Алгоритм компоновки графа можно использовать для визуализации крупномасштабного метаболического пути или филогенетических деревьев/сетей.  

Многие другие проблемы биоинформатики могут быть концептуально сведены к графическим представлениям. Обход графа, раскраска, подсчет кликов, сопоставление, поток, минимальное остовное дерево, кратчайший путь и т.д. могут быть использованы для решения различных задач.