Lower bounds on multiple sequence alignment using exact 3-way alignment |
| |
Authors: | Charles J Colbourn Sudhir Kumar |
| |
Institution: | (1) Center for Evolutionary Functional Genomics, The Biodesign Institute, Arizona State University, PO Box 875301, Tempe, AZ 85287-5301, USA;(2) School of Computing and Informatics, Arizona State University, PO Box 878809, Tempe, AZ 85287-8809, USA;(3) School of Life Sciences, Arizona State University, PO Box 875301, Tempe, AZ 85287-5301, USA |
| |
Abstract: | Background Multiple sequence alignment is fundamental. Exponential growth in computation time appears to be inevitable when an optimal
alignment is required for many sequences. Exact costs of optimum alignments are therefore rarely computed. Consequently much
effort has been invested in algorithms for alignment that are heuristic, or explore a restricted class of solutions. These
give an upper bound on the alignment cost, but it is equally important to determine the quality of the solution obtained.
In the absence of an optimal alignment with which to compare, lower bounds may be calculated to assess the quality of the
alignment. As more effort is invested in improving upper bounds (alignment algorithms), it is therefore important to improve
lower bounds as well. Although numerous cost metrics can be used to determine the quality of an alignment, many are based
on sum-of-pairs (SP) measures and their generalizations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|