Error graphs and the reconstruction of elements in groups

Levenshtein, Vladimir I. and Siemons, Johannes (2009) Error graphs and the reconstruction of elements in groups. Journal of Combinatorial Theory, Series A, 116 (4). pp. 795-815. ISSN 0097-3165

Full text not available from this repository. (Request a copy)

Abstract

Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new problem in graph theory which is also based on the consideration of metric balls of vertices, but which is distinct from the traditional packing and covering problems. This problem is motivated by applications in information transmission when redundancy of messages is not sufficient for their exact reconstruction, and applications in computational biology when one wishes to restore an evolutionary process. It can be defined as the reconstruction, or identification, of an unknown vertex in a given graph from a minimal number of vertices (erroneous or distorted patterns) in a metric ball of a given radius r around the unknown vertex. For this problem it is required to find minimum restrictions for such a reconstruction to be possible and also to find efficient reconstruction algorithms under such minimal restrictions. In this paper we define error graphs and investigate their basic properties. A particular class of error graphs occurs when the vertices of the graph are the elements of a group, and when the path metric is determined by a suitable set of group elements. These are the undirected Cayley graphs. Of particular interest is the transposition Cayley graph on the symmetric group which occurs in connection with the analysis of transpositional mutations in molecular biology [P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach, MIT Press, Cambridge, MA, 2000; D. Sankoff, N. El-Mabrouk, Genome rearrangement, in: T. Jiang, T. Smith, Y. Xu, M.Q. Zhang (Eds.), Current Topics in Computational Molecular Biology, MIT Press, 2002]. We obtain a complete solution of the above problems for the transposition Cayley graph on the symmetric group.

Item Type:	Article
Uncontrolled Keywords:	reconstruction,coding theory,biological sequence analysis,cayley graphs,stirling numbers
Faculty \ School:	Faculty of Science > School of Mathematics
UEA Research Groups:	Faculty of Science > Research Groups > Algebra and Combinatorics
Depositing User:	Vishal Gautam
Date Deposited:	18 Mar 2011 14:26
Last Modified:	16 May 2023 00:12
URI:	https://ueaeprints.uea.ac.uk/id/eprint/21026
DOI:	10.1016/j.jcta.2008.11.005

Actions (login required)

View Item