Unfortunately, the solution proposed by Sankoff [1] 20 years ago has a complexity of O(n3m) in time, and O(n2m) in space, for m sequences of length n. Thus, most structure alignment programs (e.g. DYNALIGN [2], FOLDALIGN [3], PMCOMP [4], or STEMLOC [5]) implement lightweight variants of Sankoff's algorithm, but are still computationally demanding. Consequently, researchers often create an initial sequence alignment that is afterwards corrected manually or by the aid of RNA alignment editors (e. g. CONSTRUCT [6], JPHYDIT [7], RALEE [8], or SARSE [9]) to satisfy known structural constraints. The question which alignment technique and/or program performs best under which conditions has been extensively investigated for proteins. The first exhaustive protein alignment benchmark [10] used the so called BAliBASE (Benchmark Alignment dataBASE) [11]. BAliBASE is widely used and has been updated twice since the original publication (BAliBASE 2 and 3, [12,13]). There are a number of other protein alignment databases for example HOMSTRAD [14], OXBench [15], PREFAB [16], SABmark [17], or SMART [18].