Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Reversal and Transposition Medians
Mathematical Sciences, Göteborg University and Chalmers University of Technology, Göteborg.ORCID iD: 0000-0002-6444-7878
2007 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 374, no 1-3, p. 111-126Article in journal (Refereed) Published
Abstract [en]

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 device 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.

Place, publisher, year, edition, pages
Amsterdam, Netherlands: Elsevier, 2007. Vol. 374, no 1-3, p. 111-126
National Category
Mathematics
Identifiers
URN: urn:nbn:se:oru:diva-41708DOI: 10.1016/j.tcs.2006.12.006ISI: 000246170000010Scopus ID: 2-s2.0-33947374693OAI: oai:DiVA.org:oru-41708DiVA, id: diva2:780971
Available from: 2015-01-15 Created: 2015-01-15 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Eriksen, Niklas
In the same journal
Theoretical Computer Science
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 521 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf