DIALIGN is a software program for …
DIALIGN is a software program for multiple sequence alignment developed by Burkhard Morgenstern et al. While standard alignment methods rely on comparing single residues and imposing gap penalties, DIALIGN constructs pairwise and multiple alignments by comparing entire segments of the sequences. No gap penalty is used. This approach can be used for both global and local alignment, but it is particularly successful in situations where sequences share only local homologies
Abstract.
A popular approach in comparative genomics is to locate
groups or clusters of orthologous genes in multiple genomes and to pos-
tulate functional association between the genes contained in such clus-
ters. To this end, genomes are often represented as permutations of their
genes, and common intervals, i.e. intervals containing the same set of
genes, are interpreted as gene clusters. A disadvantage of modelling
genomes as permutations is that paralogous copies of the same gene
inside one genome can not be modelled.
In this paper we consider a slightly modified model that allows paralogs,
simply by representing genomes as sequences rather than permutations of
genes. We define common intervals based on this model, and we present
a simple algorithm that finds all common intervals of two sequences in
T(n2 ) time using T(n2 ) space. Another, more complicated algorithm
runs in O(n2 ) time and uses only linear space. We also show how to
extend the simple algorithm to more than two genomes, and we present