SomeBiologicalSequenceMetrics

一些生物序列指標AbstractSomenewmetricsareintroducedtomeasurethedistancebetweenbiologicalsequences,suchasaminoacidsequencesornucleotidesequences.ThesemetricsgeneralizeametricofSellers,whoconsideredonlysingledeletions,mutations,andinsertions.Thepresentmetricsallow,forexample,multipledeletionsandinsertionsandsinglemutations.Theyalsoallowcomputationofthedistanceamongmorethantwosequences.Algorithmsforcomputingthevaluesofthemetricsaregivenwhichalsocomputebestalignments.TheconnectionwiththeinformationtheoryapproachofReichert,Cohen,andWongisdiscussed.MinimumEditDistanceProblem：給定兩個字符串A=a1a2a…an及B=b1b2…bn。并在其定義三種運算：1.插入(insert)：在字符串中插入一個字符。2.刪除(delete)：在字符串中刪除一個字符。3.替換(replace)：將字符串中的某一個字符換成另一個字符。使用以上三種運算將A序列轉到B序列，求所需運算及最小值。Recursion令Ci,j是將Ai和Bj之最短運算序列之長度，則：其中，對于所有的Ci,0=i，C0,j=j。Example：A=abaaa，B=abccaaa。Supposeallsinglemutationhaveweight1,allallsingledeletionandinsertionhaveweight1.ΔabccaaaΔ01234567a10123456b21012345a32112234a43223223a54333222DoubleDeletionandInsertionDistanceCalculationA=abaaa，B=abccaaa。Supposeallsinglemutationshaveweight1,allallsingledeletionsandinsertionshaveweight1,andalldoubledeletionsandinsertionshaveweight1.1.ΔabccaaaΔ011.12.12.23.23.34.3a1011.12.12.23.23.3b1.11011.12.12.23.2a2.11.11121.12.12.2a2.22.11.12221.12.1a3.22.22.12.13221.1MultipleAlignmentExample:a(1)=ABCBa(2)=BCCa(3)=ABC

ABCBΔ

BCCAB

CΔ?alignIdea:usedynamicprogrammingComplexityofMSAFor3sequencesoflengthn：Timecomplexity:O(n3)Forksequenceoflengthn：Timecomplexity:O(nk)

AboutAuthorMichaelWaterman教授率先將數學和計算方法引入生物學研究，在生物信息領域有許多開創(chuàng)性的貢獻，被譽為「生物信息學之父」。他致力于將數學、統(tǒng)計、計算機科學應用于各種分子生物學問題中，開辟了