Improve structural alignment datastructures

[sbliven]

BioJava contains a number of algorithms for aligning protein structures. In the most general case, an alignment consists of a mapping between residues of two (or more) proteins. However, for historical and performance reasons alignments are stored as linear, sorted arrays. This makes it difficult to express cases where the order of aligned residues differs between the two proteins. For instance, storing the following alignment requires some creative work-arounds:

 123456
 456123

Additionally, the class to store structural alignments (AFPChain) contains a number of unneccessary, poorly documented, or algorithm-specific parameters which should be removed or refactored.

AFPChain should be refactored into a new data structure that

• Is flexible enough to store topology-independent alignments
• Efficiently utilizes memory
• Has good performance for common tasks
• Works for rigid body, flexible, and local structural alignments
• Maintains consistency when modified

Suggested for GSoC 2013

[willishf]

Spencer

From a google summer of code project a couple years ago that Andreas and I
coordianted we have a very reasonable/modern sequence aligner. Details at
http://biojava.org/wiki/BioJava:CookBook#Pairwise_and_Multiple_Sequence_Alignment

The developer was a PhD student who is no longer active so this code needs
a new owner.

Scooter

On Mon, May 12, 2014 at 6:39 AM, Spencer Bliven notifications@github.comwrote:

BioJava contains a number of algorithms for aligning protein structures.
In the most general case, an alignment consists of a mapping between
residues of two (or more) proteins. However, for historical and performance
reasons alignments are stored as linear, sorted arrays. This makes it
difficult to express cases where the order of aligned residues differs
between the two proteins. For instance, storing the following alignment
requires some creative work-arounds:

123456
456123

Additionally, the class to store structural alignments (AFPChain) contains
a number of unneccessary, poorly documented, or algorithm-specific
parameters which should be removed or refactored.

AFPChain should be refactored into a new data structure that

• Is flexible enough to store topology-independent alignments
• Efficiently utilizes memory
• Has good performance for common tasks
• Works for rigid body, flexible, and local structural alignments
• Maintains consistency when modified

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/126
.

[andreasprlic]

Spencer: what is the "creative work-around" that you took to store that alignment?

[sbliven]

@willishf This issue is about structure alignment. However, I we don't have any order-independent sequence alignment algorithms either, and SequencePair wouldn't be able to store them if we did. So really the issue could be a feature request in both the structure and sequence spaces.

@andreasprlic Storing each side of the CP in a separate block in the AFPChain, then getting you to fix all the places in AFPWriter and other classes that assumed a sequential order between blocks. There are still places which assume sequential order within blocks for performance.

Basically, this issue is for a rewrite of AFPChain that I've long been thinking about. AFPChain was basically a bean for all the globals during the jFATCAT/jCE port, but now it is the core class for structure alignment. I would prefer a more conceptual data model of what constitutes an alignment. For the structure package this must include order-independent concepts to support CE-CP and derivative algorithms.

[lafita]

This should have been closed when the MultipleAlignment Data Structure (to store multiple structural alignments) was merged #278.