Aligning Genomes with Inversions and Swaps

Proceedings Of The Second International Conference On Intelligent Systems For Molecular Biology

Volume

Proceedings Of The Second International Conference On Intelligent Systems For Molecular Biology

Contents

The decision about what operators to allow and how to charge for these operations when aligning strings that arise in a biological context is the decision about what model of evolution to assume. Frequently the operators used to construct an alignment between biological sequences are limited to deletion, insertion, or replacement of a character or block of characters, but there is biological evidence for the evolutionary operations of exchanging the positions of two segments in a sequence and the replacement of a segment hy its reversed complement. In this paper we describe a family of heuristics designed to compute alignments of biological sequences assuming a model of evolution with swaps and inversions. The heuristics will necessarily be approximate since the appropriate way to charge for the evolutionary events (ddete, insert, substitute, swap, and invert) is not known. The paper concludes with a pairwise comparison of 20 Picornavirus genomes, and a detailed comparison of the hepatitis delta virus with the citrus exocortis viroid.