On the computational complexity of closest genome problems
| Autor: | Vinícius Fernandes dos Santos, Pedro Feijão, Luis Antonio Brasil Kowada, Luís Felipe I. Cunha, Celina M. H. de Figueiredo |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computational complexity theory
Applied Mathematics Breakpoint Closest string 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Computational biology Quantitative Biology::Genomics 01 natural sciences Genome 010201 computation theory & mathematics Phylogenetics Discrete Mathematics and Combinatorics Pairwise comparison Hamming code Mathematics Block (data storage) |
| Zdroj: | Discrete Applied Mathematics. 274:26-34 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.04.002 |
| Popis: | Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. One important problem is the Closest Genome Problem (CGP), that aims to find, for a given distance notion, a genome that minimizes the maximum distance to any other, which can be seen as finding a genome in the center of all others. The Hamming Closest String Problem (Hamming-CSP) was already studied and settled to be NP-complete. In this paper, we show that the CGP is NP-complete for well-known genome rearrangement distances, such as the single-cut-or-join, the breakpoint and the block interchange. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect