CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Reversal and Transposition Medians

Niklas Eriksen (Institutionen för matematiska vetenskaper)
Theoretical Computer Science Vol. 374 (2007), p. 111-126.
[Artikel, refereegranskad vetenskaplig]

In determining phylogenetic trees using gene order information, medians provide a powerful alternative to pairwise distances. On the other hand, both breakpoint and reversal medians are NP-hard to compute and the use of medians has been limited to relatively closely related genomes. In this paper, we show that in spite of the greater non-uniqueness of reversal medians, compared to breakpoint medians, medians of moderately distant genomes are often widely spread. This means that regardless of which approximation algorithms one may devise for computing reversal medians, the genomes need to be closely related for phylogenetic tree computations to be successful. To show this, we use results on transposition medians, which behave similarly, and also support our claims with simulations and a real data example with widely spread medians.

Nyckelord: Median; Reversal; Transposition; Genome rearrangement

Denna post skapades 2007-08-22.
CPL Pubid: 45426


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)


Diskret matematik
Teoretisk datalogi

Chalmers infrastruktur