动态规划法——编辑距离.ppt

*/92AligningSequenceswithoutInsertionsandDeletions:HammingDistanceGiventwoDNAsequencesvandw:v:TheHammingdistance:dH(v,w)=8islargebutthesequencesareverysimilarATATATATATATATATw:*/92AligningSequenceswithInsertionsandDeletionsv:ATATATATATATATATw:----Byshiftingonesequenceoveroneposition:Theeditdistance:dH(v,w)=2.HammingdistanceneglectsinsertionsanddeletionsinDNA*/92EditDistanceLevenshtein(1966)introducededitdistancebetweentwostringsastheminimumnumberofelementaryoperations(insertions,deletions,andsubstitutions)totransformonestringintotheotherd(v,w)=MINnumberofelementaryoperationstotransformv?w*/92EditDistancevsHammingDistanceV=ATATATATW=TATATATAHammingdistancealwayscomparesi-thletterofvwithi-thletterofwHammingdistance:d(v,w)=8ComputingHammingdistanceisatrivialtask.*/92EditDistancevsHammingDistanceV=ATATATATW=TATATATAHammingdistance:Editdistance:d(v,w)=8d(v,w)=2ComputingHammingdistanceComputingeditdistanceisatrivialtaskisanon-trivialtaskW=TATATATAJustoneshiftMakeitalllineupV=-ATATATATHammingdistancealwayscomparesi-thletterofvwithi-thletterofwEditdistancemaycomparei-thletterofvwithj-thletterofw*/92EditDistancevsHammingDistanceV=ATATATATW=TATATATAHammingdistance:Editdistance:d(v,w)=8d(v,w)=2(oneinsertionandonedeletion)Howtofindwhatjgoeswithwhati???W=TATATATAV=-ATATATATHammingdistancealwayscomparesi-thletterofvwithi-thletterofwEditdistancemaycomparei-thletter