La bioinformática plantea regularmente nuevos desafíos a los ingenieros de algoritmos y científicos informáticos teóricos. Este trabajo analiza los desarrollos recientes de algoritmos parametrizados y complejidad para importantes problemas NP-duros en bioinformática. Cubrimos el ensamblaje y análisis de secuencias, la comparación y completado de genomas, y la haplotipificación y filogenética. Además de informar sobre el estado del arte, planteamos desafíos y problemas abiertos para cada tema.