Algorithm engineering for optimal alignment of protein structure distance matrices

Details Algorithm engineering for optimal alignment of protein structure distance matrices Algorithm engineering for optimal alignment of protein structure distance matrices

2011-04-15

arxiv.org/abs/1104.2995v1

Optimization Letters (2011)

Biology

Quantitative Biology

Quantitative Methods

Scientific paper

10.1007/s11590-011-0313-3

Protein structural alignment is an important problem in computational biology. In this paper, we present first successes on provably optimal pairwise alignment of protein inter-residue distance matrices, using the popular Dali scoring function. We introduce the structural alignment problem formally, which enables us to express a variety of scoring functions used in previous work as special cases in a unified framework. Further, we propose the first mathematical model for computing optimal structural alignments based on dense inter-residue distance matrices. We therefore reformulate the problem as a special graph problem and give a tight integer linear programming model. We then present algorithm engineering techniques to handle the huge integer linear programs of real-life distance matrix alignment problems. Applying these techniques, we can compute provably optimal Dali alignments for the very first time.

Affiliated with

Also associated with

No associations

Rating

Algorithm engineering for optimal alignment of protein structure distance matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithm engineering for optimal alignment of protein structure distance matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm engineering for optimal alignment of protein structure distance matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8543