Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 175 - 189 DOI 10.1051/ita:2005011

Theoret. Informatics Appl. 39, 175-189 (2005)
DOI: 10.1051/ita:2005011

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira do Lago¹, Ilya Muchnik² and Casimir Kulikowski<sup>2

1</sup>  Universidade de São Paulo, Brasil; alair@ime.usp.br
²  Rutgers University

Abstract
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown. In 1992, Schöniger and Waterman proposed the simplification hypothesis that the inversions do not overlap. They also presented an O(n⁶) exact solution for the alignment with non-overlapping inversions problem and introduced a heuristic for it that brings the average case complexity down. (In this work, n is the maximal length of both sequences that are aligned.) The present paper gives two exact algorithms for the simplified problem. We give a quite simple dynamic program with O(n⁴)-time and O(n²)-space complexity for alignments with non-overlapping inversions and exhibit a sparse and exact implementation version of this procedure that uses much less resources for some applications with real data.

Mathematics Subject Classification. 05C85, 68R15, 90C27, 90C39


© EDP Sciences 2005

What is OpenURL?