On the Design of Optimization Criteria for Multiple Sequence Alignment?

Abstract. Multiple sequence alignment (MSA) is important in functional, struc-tural and evolutionary studies of sequence data. While MSA construction has tradi-tionally been an interactive process, the rapid growth of genetic sequence data has engendered a need for automated sequence analysis without human intervention. This requires more accurate methods based on rigorous mathematical models that reflect sequence biology in a realistic way. Focusing on MSA as an optimization problem, we examine the problem of unifying mathematical tractability with bio-logical accuracy in cost function design. In particular, we consider tree alignment, which is often viewed as the most “biological ” of the rigorous approaches to MSA. We point out several important pitfalls in current optimization approaches to MSA and identify characteristics for good cost function design. Design issues specific to approximation algorithms are also addressed. We hope these ideas will lead to fu-ture research on a biologically realistic and mathematically rigorous approach to MSA.