Editing Structural alignment (section)

==Algorithmic complexity==

===Optimal solution===
The optimal "[[protein threading|threading]]" of a protein sequence onto a known structure and the production of an optimal multiple sequence alignment have been shown to be [[NP-complete]].<ref name="lathrop"/><ref name="wang"/> However, this does not imply that the structural alignment problem is NP-complete. Strictly speaking, an optimal solution to the protein structure alignment problem is only known for certain protein structure similarity measures, such as the measures used in protein structure prediction experiments, GDT_TS<ref name="zemla" /> and MaxSub.<ref name="fischer"/> These measures can be rigorously optimized using an algorithm capable of maximizing the number of atoms in two proteins that can be superimposed under a predefined distance cutoff.<ref name="poleksic"/> Unfortunately, the algorithm for optimal solution is not practical, since its running time depends not only on the lengths but also on the intrinsic geometry of input proteins.

===Approximate solution===
Approximate [[polynomial-time]] algorithms for structural alignment that produce a family of "optimal" solutions within an approximation parameter for a given scoring function have been developed.<ref name="poleksic" /><ref name="kolodny"/> Although these algorithms theoretically classify the approximate protein structure alignment problem as "tractable", they are still computationally too expensive for large-scale protein structure analysis. As a consequence, practical algorithms that converge to the global solutions of the alignment, given a scoring function, do not exist. Most algorithms are, therefore, heuristic, but algorithms that guarantee the convergence to at least local maximizers of the scoring functions, and are practical, have been developed.<ref name="lovo1"/>