Optimal solutions for hard problems in computational biology

生物算法在生物学、化学、信息学和数学领域的研究中具有独特性和交叉性。这是一个复杂的自然现象，其复杂程度也很高。分子生物学家约瑟夫·费尔森斯坦（Joseph Felsenstein）在1998年写道：“大约十年前，一些计算机科学家来过，说他们听说我们有一些非常酷的问题。他们证明了这些问题是NP完全的，并且消失了。“Die Untersuchung der Handhabbarkeit kombinatorisch schwieriger Probleme der Molekularbiologie ist das zentrale Anliegen dieses Projekts. Schwerpunkt是一种具有最佳吸收和保证Laufzeitschranken的高效率的工具。因此，它是一个复杂的生物学问题的参数化问题。Kernidee der parametrisierten Komplexität is es，die“kombinatorische Explosion”，z.B.在NP-问题中，通过一个参数来确定最优参数，而不是仅仅确定最优参数。该节日参数的实施工作由我们进行，并进行了详细的讨论，以使Laufzeitverhalten weiter verbessern。[...]我们与生物学和生物化学的合作伙伴共同研究了DNA测序分析中的系统发生学、引物设计、动机和基因组学等问题。

Die algorithmische Biologie hat sich zu einem unabhängigen und interdisziplinären Forschungsgebiet im Querschnitt der Bereiche Biologie, Chemie, Informatik und Mathematik entwickelt. Viele Probleme aus diesem Bereich sind kombinatorischer Natur und erweisen sich als von hoher Berechnungskomplexität. Der Molekularbiologe Joseph Felsenstein wird 1998 wie folgt zitiert: "About ten years ago some computer scientists came by and said they heard we have some really cool problems. They showed that the problems were NP-complete and went away."Die Untersuchung der Handhabbarkeit kombinatorisch schwieriger Probleme der Molekularbiologie ist das zentrale Anliegen dieses Projekts. Der Schwerpunkt liegt dabei auf exakten Algorithmen mit optimalen Lösungen und garantierten Laufzeitschranken. Insbesondere ist unser Anliegen, die parametrisierte Komplexität von biologischen Problemen zu ermitteln. Kernidee der parametrisierten Komplexität ist es, die "kombinatorische Explosion", z.B. bei NP-harten Problemen, auf einen Parameter einzuschränken und dadurch schnelle Algorithmen mit optimalen und nicht nur angenäherten Lösungen zu erhalten. Die Implementierung dieser Festparameter-Algorithmen ergänzen wir mit heuristischen Strategien und können so das Laufzeitverhalten weiter verbessern. [...]In Zusammenarbeit mit Partnern aus Biologie und Biochemie arbeiten wir an harten kombinatorischen Problemen in der Analyse von DNA-Sequenzen wie Phylogenetik, Primer-Design, Motivsuche und Genomvergleich.