一些生物序列指标

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教授率先将数学和计算方法引入生物学研究，在生物信息领域有许多开创性的贡献，被誉为「生物信息学之父」。他致力于将数学、统计、计算机科学应用于各种分子生物学问题中，开辟了