Enumeration and symmetry of edit metric spaces

Thumbnail Image
Date
2005-01-01
Authors
Campbell, Jessie
Major Professor
Advisor
Daniel Ashlock
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
Abstract

This thesis addresses the problem of enumerating the size of the k-spheres of a fixed word for the edit metric as well as discussing the symmetry group of the edit graph in order to create an edit metric error correcting code. The application of such error correcting codes is to the correction of sequencing errors in DNA barcodes, short stretches of DNA incorporated into genomic libraries to identify source tissue or other information about the source of a given DNA sequence. As sequencing errors not only substitute characters but potentially insert and delete them, the traditional Hamming metric used in standard error correcting codes is not useful. The natural metric, the edit distance, is algebraically complex as compared to the Hamming metric. In this thesis the exact size of edit spheres of radius 1 and 2 are computed for any binary or q-ary string. The number of edit distance d neighbors of two special types of strings is also presented. Structural information about the edit metric space, in particular a representation as a pyramid of hypercubes and the symmetry group of the space, is given. This result begins the process of reconstructing the theory of error correcting codes for the edit metric and yields practical advice for the design of heuristic algorithms, e.g. evolutionary algorithms, used in practice to create error correcting DNA barcodes.

Comments
Description
Keywords
Citation
Source
Subject Categories
Keywords
Copyright
Sat Jan 01 00:00:00 UTC 2005