Maximum Likelihood Star Alignment of Multiple Molecular Sequences

Abstract

In the study of pairwise sequence alignment, a clear relationship between the scoring system and assumptions about the occurrence of evolutionary events has been established in [BT86], [TKF91], [TKF92] and [TC95] by proposing an evolutionary model. To align two given sequences, one need estimate some evolutionary parameters through maximum likelihood method, and find an alignment with the maximum probability using the estimated parameters. In this thesis, we extend the above model and the maximum likelihood method to star alignment of three molecular sequences along the same line. We overcome the duplications of star alignments by defining canonical star alignments. Two star alignment algorithms, i.e. sum approach and direct alignment approach, are proposed in this thesis based on two different likelihood functions. A software system, called MLSAS (Maximum Likelihood Star Alignment System), is developed to implement the two algorithms with a friendly graphical user interface. Simulation studies show their behaviors are satisfactory for closely related sequences. A few real examples are also provided.