Parametric Alignment of Drosophila Genomes
Here we present the alignment polytopes and software for the paper
"Parametric Alignment of Drosophila Genomes."
Segments of the Drosophila melanogaster genome that have been
parametrically aligned with orthologous segments of the Drosophila
pseudoobscura genome may be visualized through this UCSC
Genome Browser custom track.
As part of our whole genome parametric alignment of Drosophila
melanogaster and Drosophila pseudoobscura, we have produced
alignment polytopes for the set of transcription factor binding sites
available at the Drosophila
DNase I Footprint Database. To view the polytopes for segments
overlapping these elements, load the UCSC
Genome Browser custom track with the "FlyReg" track turned on.
We have implemented two algorithms for the parametric alignment of two
DNA sequences: the polytope-propagation algorithm, and the
beneath-beyond algorithm. The polytope-propagation algorithm
can compute the alignment polytope for two sequences for scoring
schemes with any number of parameters. However, it is quite slow due
to the fact that it repeatedly peforms expensive convex hull
computations. The beneath-beyond algorithm is much faster, and its
current implementation can handle scoring schemes of dimension up to
five. On current hardware, the beneath-beyond implementation can
produce the 3d alignment polytope of two sequences of length 150bp in
less than one second. Implementations of both algorithms are made
available here and have identical interfaces.
Available here are Linux binaries for the two programs. Binaries for
other platforms may be available on request.
To obtain help on running these programs, execute them on the command
line with the "--help" option.
The source code for the implementation of the polytope-propagation
algorithm is available as part of Colin
Dewey's source code package. Source code for the beneath-beyond
implementation will be made available soon.
The parametric alignment programs can take as input a symbolic scoring
matrix. The default scoring scheme is the Jukes-Cantor scoring matrix
with affine gap scores (a 3d model). Here are matrices for the phylogenetic models
JC69, K80, K81, SYM.