Inicio  /  Algorithms  /  Vol: 12 Par: 12 (2019)  /  Artículo
ARTÍCULO
TITULO

Parameterized Algorithms in Bioinformatics: An Overview

Laurent Bulteau and Mathias Weller    

Resumen

Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic.

 Artículos similares

       
 
Johannes K. Fichte, Markus Hecher, Michael Morak and Stefan Woltran    
Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been establish... ver más
Revista: Algorithms

 
Max Bannach and Till Tantau    
Color coding is an algorithmic technique used in parameterized complexity theory to detect ?small? structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pat... ver más
Revista: Algorithms

 
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee and Pasin Manurangsi    
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspect... ver más
Revista: Algorithms

 
Neeldhara Misra, Frances Rosamond and Meirav Zehavi    
This Special Issue contains eleven articles?surveys and research papers?that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to... ver más
Revista: Algorithms

 
Faisal N. Abu-Khzam and Karam Al Kontar    
This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions. In particular, we present a general view of how known ??... ver más
Revista: Algorithms