Multichromosomal median and halving problems under different genomic distances

BMC Bioinformatics

Table 1 Results summary.

problem context: distance, #chr, linear, circular or mixed	distance	halving	double distance	median	guided halving
breakpoint unichr, circular or linear	P	open	open	NP [20, 21]	open
breakpoint multichr, circular and mixed	P new	P new	P new	P new	P new
breakpoint multichr, linear	P new	open P?	P new	NP new	NP [27]
DCJ unichr, circular or linear	P [3, 12]	P [16]	open	NP [22]	open
DCJ multichr, circular and mixed	P [3, 12]	P [4, 5]	NP new	NP new	NP new
DCJ multichr, linear	P [12]	open	open	open NP?	open NP?
RT unichr	P [39]	open	open	NP [22]	open
RT multichr	P [17, 33–35]	P [32]	open NP?	open NP?	open NP?

Status of complexity questions for five problems related to ancestral genome reconstruction, for eight genomic distances in the unichromosomal and multichromosomal contexts. Note that unichromosomal problems require that both input and output genomes be unichromosomal, so all problems involving doubled genomes are computationally defined in the circular case, when the doubled genome consists in a single circular chromosome composed of two successive occurences of the ordinary genome. Other versions of the halving problem are less restrictive [5, 16, 32]. P and NP stand for polynomial and NP-hard, respectively, and when followed by ?, represent our conjectures.

ISSN: 1471-2105