Quasi-median hulls in Hamming space are Steiner hulls

Link:
Autor/in:
Erscheinungsjahr:
2009
Medientyp:
Text
Schlagworte:
  • Graph in graph theory
  • Vertex of a graph
  • Detour monophonic
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Graph in graph theory
  • Vertex of a graph
  • Detour monophonic
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • A Hamming space Lambda(n) consists of all sequences of length n over an alphabet Lambda and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u, v, w the sequence which in each coordinate attains either the majority coordinate from u, v, w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Lambda(n) the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Lambda(n) there exists a shortest realization within Lambda(n) for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space. (C) 2008 Elsevier B.V. All rights reserved.
  • A Hamming space Λn consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u, v, w the sequence which in each coordinate attains either the majority coordinate from u, v, w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λn the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λn there exists a shortest realization within Λn for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space. © 2008 Elsevier B.V. All rights reserved.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/98fd04be-6f02-488a-b907-e9cf8b8b5e3c