DESIGNING A TIGHTER SEARCHING SPACE FOR PAIRWISE GLOBALSEQUENCE ALIGNMENTS OVER MULTIPLE SCORING SYSTEMS

摘要

The need to repeat alignments on a pair of amino acidresidue sequences to select an appropriate scoring functionand detect a significance of score arises in genomics and proteomics.While computing the alignments obtained through aset of typical scoring matrices with the corresponding defaultgap cost, we observe that many aligned segments are sharedwith a reference global alignment. We show that parametersextracted from the search for an alignment corresponding toa good scoring system can be used to predict the deviationof alignments computed with respect to different scoring matrices.By training sample pairs of protein sequences fromSCOP 1:71 of the ASTRAL database, we build the approximatedprobability distribution of distance from a node ona reference path to the alignments based on other scoringschemes with respect to the proposed parameters. We showthat the overall computational cost to perform alignments using‘three’ scoring matrices and the proposed method can bereduced to 11% of a normal Needleman-Wunch global alignmentwith an average 92% accuracy.