| Definition
|
<br />
DIALIGN is a software progra … <br />
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<br />
Abstract.<br />
A popular approach in comparative genomics is to locate<br />
groups or clusters of orthologous genes in multiple genomes and to pos-<br />
tulate functional association between the genes contained in such clus-<br />
ters. To this end, genomes are often represented as permutations of their<br />
genes, and common intervals, i.e. intervals containing the same set of<br />
genes, are interpreted as gene clusters. A disadvantage of modelling<br />
genomes as permutations is that paralogous copies of the same gene<br />
inside one genome can not be modelled.<br />
In this paper we consider a slightly modified model that allows paralogs,<br />
simply by representing genomes as sequences rather than permutations of<br />
genes. We define common intervals based on this model, and we present<br />
a simple algorithm that finds all common intervals of two sequences in<br />
T(n2 ) time using T(n2 ) space. Another, more complicated algorithm<br />
runs in O(n2 ) time and uses only linear space. We also show how to<br />
extend the simple algorithm to more than two genomes, and we present<br />
results from the application of our algorithms to real data.<br /> f our algorithms to real data.<br />
|
