Shen S., Tuszynski J.A. Theory and Mathematical Methods for Bioformatics

Подождите немного. Документ загружается.

138 4 Super Pairwise Alignment

Table 4.5. Data for two RNA sequences: Mc.vanniel and Mb.tautotr

1 uaucuauuac ccuacccugg ggaauggcuu ggcuugaaac gccgaugaag gacgugguaa gcugcgauaa gccuaggcga

ggcgcaacag ccuuugaacc uaggauuucc gaaugggacu uccuacuuuu guaauccgua aggauuggua acgcggggga

161 uugaagcauc uuaguacccg caggaaaaga aaucaacuga gauuccguua guagaggcga uugaacacgg aucagggcaa

acugaauccc uucggggaga ugugguguua uagggccuuc uuuucgccug uugagaaaag cugaaguuga cuggaacguc

321 acacuauaga gggugaaagu cccguaagcg caaucgauuc agguuugaag ugucccugag uaccgugcgu uggauaucgc

gcgggaauuu gggaggcauc aacuuccaac ucuaaauacg uuucaagacc gauagcguac uaguaccgcg agggaaagcu

481 gaaaagcacc cuuaacaggg uggugaaaag agccugaaac ccagguaggu auggaauggc guggccccaa aggcaacugu

ucugaaggaa accgucgcaa ggcggcugua cgaagaacag agccaggguu gcguccuccg uuucgaaaaa cgggccgggg

641 aguguauugu uguggcgagc uuaagaucuu cacgaucgaa ggcguaggga aaccaacaag uccgcagaau cuuuagggac

ggggucuuaa gggcccggag ucacagcaau acgacccgaa accgggcgau cuaggccggg gcaaggugaa gucccucaau

801 ugagggaugg aggccugcag aguuguugcc guucgaagca cucuucugac cucggucuag gggugaaagg ccaaucgagc

ccggagauag cugguucccc ucgaagugac ucucagguca gccagaguuc agguagucgg caggguagag cacugauaag

961 augguuaggg gaagaaauuc cucgcuguuu ugucaaacuc cgaaccuguc gucgccguag gcucugagug agggcauacg

ggguaagcug uauguccgag acgggaauag ccgagacuug gguuaaggcc ccuaaaugcc gauuaagugu gaacacgaag

1121 ggcguccuug gucuaagaca gcagggaggu uggcuuagaa gcagccaccc uuuaaagagu gcguaacagc ucaccugucg

agaucaaggg ccccgaaaau ggacggggcu aaaucggcug ccgagaccca aagggcaccg caaggugauc cccguagggg

1281 ggcguucugc gagggcagaa guucggcugu gaagucgagu ggaccucgua gaaaugaaga ucccgguagu aguaacagca

uaaguggggu gagaaucccc accgccgaag gggcaagggu uccacagcaa uguuugucag cuguggguaa gccgguccua

1441 acucucgagg uaacuccuuu gagaggaaag ggaaacaggu uaauauuccu gugccaucua gauacgcgug gcaacacaag

guuaguuucc aacgcuucug gguaggcuga guguucuugu cuggacauuc aagcuuauaa guccggggag aguuguaaua

1601 acgagaaccg gaugaaagag ugaugagcuc uccguuagga gaguucggcc gaucucugga gcccgugaaa agggaacuag

caaggauucu agauguccgu acccagaacc gacacuggug ccccuaggug aguauccuaa ggcguagcgg gaugaaucua

1761 gucgagggaa gucggcaaau ugguuccgua acuucgggag aaggagugcc agugaucuug uuuaaauaug ggaucgcugg

ucgcagugac cagggagguc cgacuguuua auacaaacau aggucuuagc gagccugaaa agguguguac uaaggccgac

1921 gccugcccag ugcugguacg ugaaccccgg uuccaaccgg gcgaagcgcc aguaaacggc ggggguaacu auaacccucu

uaagguagcg aaauuccuug ucgggcaagu uccgaccugc augaauggcg uaacgagacc uccacugucc ccgacuagaa

2081 uccggugaac cuaccauucc ggcgcaaagg ccggagacuu ccagugggaa gcgaagaccc cguggagcuu uacugcagcc

ugucguuggg gcaugguugu gaguguacag uguagguggg agccaucgaa accuuuucgc caggaaaggu ggaggcgauc

2241 cugggacacc acccucucau gaccauguuc cucacccuuu uaggggacac cgguaggugg gcaguuuggc uggggcggua

cccuccuaaa aaugcaucag gagggcccca aagguuggcu caagcggguc aggacuccgc uguugagugu aagggcaaaa

2401 gccagccuga cuuuguugcc aacaaaacgc aacgaagagg cgaaagccgg gccuaacgaa ccccugugcc ucacugaugg

gggccaggga ugacaaaaaa gcuaccccgg ggauaacaga guugucgcgg gcaagagccc auaucgaccc cgcggcuugc

2561 uaccucgaug ucgguuuuuc ccauccuggg ucugcagcag gacccaaggg uggggcuguu cgcccauuaa aggggaucau

gagcuggguu uagaccgucg ugagacaggu ugguugcuau cugcuggaug uguuaggcug ucugagggaa agguggcucu

2721 aguacgagag gaacgggccg ucggcgccuc uagucgaucg guugucugac aaggcacugc cgagcagcca cgcgccaaga

gccguuuccu ucgggaacga gaacucccgu agaagacggg uuugauaggc uaggggugua cgcaucaagg uucuuccgag

2881 auguucagcc cgcuaguacu aacaguucga gagauaauuu aggcauc

4. Based on the above output, we determine that the sequences Mc.vanniel

and Mb.tautotr are homologous. Following from the data of (A



), we

know that this alignment is not the minimum penalty alignment, and we

use local modiﬁcation operations to reduce the penalty.

5. In 1999, we performed this alignment using a Pentium 586 computer,

which took 0.679 s.

The Modulus Structure of this Sequence Alignment

Based on the initial data (A, B) in Table 4.5 and the aligned sequence (A



)

in Table 4.6 using the SPA, we obtain the modulus structure from (A, B)to



) as follows:

1. The numbers of shifting mutations are k



=19,k



=9,andthelength

of the aligned sequence is n



= n



= 3061. The total error of the aligned

sequences is w(A



) = 1013. The similarity of the aligned sequences is

r(A



)=1−



w(A



)=1−

1013

3061

=0.6690 .

4.4 Applications of Sequence Alignment and Examples 139

Table 4.5. (continued)

1 cuuuuuuaug ccgucugggg gauggcuugg cuugagucgc ugaugaaggc cguggcaagc ugcgauaagc ccaggggagg

agcagcaucc uuggauccug ggauugccga augggacuuc ccagccaacc cuucgggguu gugcuacucc cuguuauggg

161 gagggggaac ccgccgaacu gaaacaucuu aguaggcgga ggaagagaaa gcaaauugcg acugccguga guaauggcga

augaaagcgg ugcaggacaa acugaacccc uucgcaguga uguguugggg gauguggugu ugucgaucgg ugcguauggg

321 ggugccgggu gugugguguu gaacuugggc uggaaugccc gggccguaga ggguuaaagc cccguagaug cccaugcuug

gcucccugca ccuuuccuga guagcgucca uuggauauug ggcgugaagc ugggaggcau cgacuccuaa uccuaaacac

481 gucucaaguc cgauagcgaa cuaguaccgu gagggaaagc ugaaaaguac cccugauagg ggugugaaaa gugccugaaa

ccaggcggug acagcccggc acggcaugga aggaaugugg cugccccugu aagaaaccau gguaacaugg gaguaugugu

641 gggugguuga acagugucgu gucguccguc uugaaacacg ggccagggag uuuagugguu guggcgaggc uaagaagugu

gucgcuuugu agucguaggg aaaccgacag guccgcagca gccuuugugc ugugagggac ggggucuuaa uagggccugg

801 agucacagcu cuaaaacccg aagccggucg aucuagcccu ggguagggug aagucgcucu uacgagugau ggaggcccgc

agggguguug ucgugcgaaa cauuccucua accugggguu aguggugaaa ggccaaucaa ggccggugac agcugguucc

961 acccgaaaug gcucguaggc cagccugacu ggagauaggu ggcgggguag agcacuuauu ggguguuuag ggggagagau

cccucggcau ccuguaaaac uccgaacucg ucaccgucgu ugaagguugg agucaggggc gcgggguaag ccuguguccc

1121 gagagaggaa caacucagac ugggguuaag gucccuaaau gccggcuaag ucuaaggggg ucuuuggccc uagacaaugg

gaaggugggc uuagaagcag ccauccuuua aagaguucgu aacagaucac ccaucgaggu caaaggcacc gaaaauggag

1281 gggaauuaag ccggcuaccg auaccucaga gcaccacugg uguggugguc uuguagggug gcguccgguu gggguugaag

ugggggcgug agcuccugug gacccggcug gaaugaggau ccugguagua guagcagcga agugaggugu gaauccuuac

1441 cgccggaggg gcuaggguuc cuuggcaaug uucgucagcc aaggguuagu cgguccuaag gccgugggua auguccauuu

uggucgaaag gguaacgggu uaauauuccu guacggucca gguacuugcg gugacgcugg guugggcuuc ugacgcuuug

1601 ggguaggcug agcgggauuu ucguccuguu uaaggguuga agccugggga gagccguaau ggcgagaacc auggugaagg

ccugaauagc caucccuugu gggugguuug gcugugcccu ggaguccuug aaaagggagu ccuucuuggg auccuggauc

1761 gccguaccga gauccgacac uggugccccu agcugaguag gcuaaggugu guugggguaa ccuggcuaag ggaaaucggc

aaauuggccc cguaacuuug ggagaagggg ugccagccau gcggauggcu ggucgcagug acaggggggg cccgacuguu

1921 uaauaaaaac auagcuccua gcuagcccgu gagggugugu acugggggcg acaccugccc agugccggca cgugaagccc

ugguucaacg gggugaagcg ccgguaaacg gcggggguaa cuauaacccu cuuaagguag cgaaaugccu ugccggauaa

2081 guaccggccu gcaugaaugg uugaacgagg ucccuacugu cccuagccag gaccuaguga agcugcuguu cuggugcaca

agccagagac ucccaguggg aagcgaagac cccguagagc uuuacugcag ucugcuguug gggcuugguc auggguaugc

2241 aguguaggug ggaggcgucg augccauggu cgccaggcug ugguggaguc ggucaugaga caccaccuuc cugugacugu

gucucuaacc ccauguuugu gggggacauc gguagauggg caguuuggcu ggggcggcac gcgcuugaaa ugguaucaag

2401 cgcgcccuaa ggucggcuca ggcgggacag agauccgcug uagaguguaa gggcauaagc cggcuugacu gugcuccuac

uaguaggggg ugcaggugcg agagcagggc cuagcgaacc ccagaguccu cgucgguggg ggccugggau gacagaaaag

2561 cuaccucggg gauaacuggg uggucgcagg caagagccca uaucgacccu gcggcuugcu acuucgaugu cgguucuuuc

cauccugggu gugcagcagc acccaagggu gggguuguuc gcccauuaaa ggggaacgug agcuggguuu agaccgucgu

2721 gagacagguu gguugcuauc uacugggagu gugugguugc cugaggggaa ggugguucca guacgagagg aacggaccgu

cggcgccucu gguuuaccgg uuauccgagu ggguauugcc gggcggcuac gcgcuaugau uauaaaggcu gaaggcaucu

2881 aagccugagg uuuucccuga aaauaggugg cuuguggacu gcggguagaa gaccuguuug uuggggcggg ggugugagcu

ucgaggccug uuuugggccg aguuguuuag ccugccguuu ccaagguuuu uugucccu

2. The expanded modes of the aligned sequences are



= {(121, 20), (210, 2), (318, 20), (386, 1), (567, 4), (632, 3), (696, 3),

(766, 9), (781, 2), (1102, 1), (1331, 3), (1508, 2), (1591, 1),

(1676, 1), (1733, 3), (2288, 2), (2337, 5), (2541, 1), (2878, 1)} ,



= {(0, 2), (1192, 7), (1421, 1), (1817, 1), (1887, 12),

(2418, 1), (2987, 8), (3040, 1), (3051, 10)} ,

(4.40)

where (j

,

) are the position and length of insertion in sequence A



(or B



), respectively.

3. We ﬁnd the shifting function of sequence A



(or B



)as



(k) ,k=1, 2, ··· ,k



(k) ,k=1, 2, ··· ,k



140 4 Super Pairwise Alignment

Table 4.6. Alignment output for Mc.vanniel and Mb.tautotr

1 uaucuauuac ccuacccugg ggaauggcuu ggcuugaaac gccgaugaag gacgugguaa gcugcgauaa gccuaggcga

--cuuuuuua ugccgucugg gggauggcuu ggcuugaguc gcugaugaag gccguggcaa gcugcgauaa gcccagggga

ggcgcaacag ccuuugaacc uaggauuucc gaaugggacu u--------- ---------- -ccuacuuuu guaauccgua

ggagcagcau ccuuggaucc ugggauugcc gaaugggacu ucccagccaa cccuucgggg uugugcuacu cccuguuaug

161 aggauuggua acgcggggga uugaagcauc uuaguacccg caggaaaaga --aaucaacu gagauuccgu uaguagaggc

gggaggggga acccgccgaa cugaaacauc uuaguaggcg gaggaagaga aagcaaauug cgacugccgu gaguaauggc

gauugaacac ggaucagggc aaacugaauc ccuucgggga gauguggugu uauagggccu ucuuuucgcc uguugaga--

gaaugaaagc ggugcaggac aaacugaacc ccuucgcagu gauguguugg gggauguggu guugucgauc ggugcguaug

321 ---------- --------aa agcugaaguu gacuggaacg ucacacuaua gagggugaaa gucccg-uaa gcgcaaucga

ggggugccgg guguguggug uugaacuugg gcuggaaugc ccgggccgua gaggguuaaa gccccguaga ugcccaugcu

uucagguuug aagugucccu gaguaccgug cguuggauau cgcgcgggaa uuugggaggc aucaacuucc aacucuaaau

uggcucccug caccuuuccu gaguagcguc cauuggauau ugggcgugaa gcugggaggc aucgacuccu aauccuaaac

481 acguuucaag accgauagcg uacuaguacc gcgagggaaa gcugaaaagc acccuuaaca ggguggugaa aagagccuga

acgucucaag uccgauagcg aacuaguacc gugagggaaa gcugaaaagu accccugaua ggggugugaa aagugccuga

aacccag--- -guagguaug gaauggcgug gccccaaagg caacuguucu gaaggaaacc gucgcaaggc gg---cugua

aaccaggcgg ugacagcccg gcacggcaug gaaggaaugu ggcugccccu guaagaaacc augguaacau gggaguaugu

641 cgaagaacag agccaggguu gcguccuccg uuucgaaaaa cgggccgggg agugua---u uguuguggcg agcuuaagau

gugggugguu gaacaguguc gugucguccg ucuugaaaca cgggccaggg aguuuagugg uuguggcgag gcuaagaagu

cuucacgauc gaaggcguag ggaaaccaac aaguccgcag aaucuu---- -----uaggg a--cgggguc uuaagggccc

gugucgcuuu guagucguag ggaaaccgac agguccgcag cagccuuugu gcugugaggg acggggucuu aauagggccu

801 ggagucacag caauacgacc cgaaaccggg cgaucuaggc cggggcaagg ugaagucccu caauugaggg auggaggccu

ggagucacag cucuaaaacc cgaagccggu cgaucuagcc cuggguaggg ugaagucgcu cuuacgagug auggaggccc

gcagaguugu ugccguucga agcacucuuc ugaccucggu cuagggguga aaggccaauc gagcccggag auagcugguu

gcaggggugu ugucgugcga aacauuccuc uaaccugggg uuagugguga aaggccaauc aaggccggug acagcugguu

961 ccccucgaag ugacucucag gucagccaga guucagguag ucggcagggu agagcacuga uaagaugguu aggggaagaa

ccacccgaaa uggcucguag gccagccuga cuggagauag guggcggggu agagcacuua uuggguguuu agggggagag

auuccucgcuguuuugucaa acuccgaacc ugucgucgcc guaggcucug agugagggca ua-cggggua agcuguaugu

aucccucggcauccuguaaa acuccgaacu cgucaccguc guugaagguu ggagucaggg gcgcggggua agccuguguc

1121 ccgagacgggaauagccgag acuuggguua aggccccuaa augccgauua agugugaaca cgaagggcgu ccuuggucua

ccgagagaggaacaacucag acugggguua aggucccuaa augccggcua agucuaaggg ggucuuuggc cc-------u

1281 agacagcagg gagguuggcu uagaagcagc cacccuuuaa agagugcgua acagcucacc ugucgagauc aagggccccg

agacaauggg aaggugggcu uagaagcagc cauccuuuaa agaguucgua acagaucacc caucgagguc aaaggcaccg

aaaauggacg gggcuaaauc ggcugccgag acccaaaggg caccgcaagg u---gauccc cguagggggg cguucugcga

aaaauggagg ggaauuaagc cggcuaccga uaccucagag caccacuggu gugguggucu uguagggugg cguccgguug

1441 gggcagaagu ucggcuguga agucgagugg accucguaga aaugaagauc ccgguaguag uaacagcaua agugggguga

ggguugaagu gggggcguga gcuccugugg acccggcugg aaugaggauc cugguaguag u-agcagcga agugaggugu

gaauccccac cgccgaaggg gcaaggguuc cacagcaaug uuugucagcu guggguaagc cgguccua-- acucucgagg

gaauccuuac cgccggaggg gcuaggguuc cuuggcaaug uucgucagcc aaggguuagu cgguccuaag gccgugggua

1601 uaacuccuuu gagaggaaag ggaaacaggu uaauauuccu gugccaucua gauacgcgug gcaacacaag g-uuaguuuc

auguccauuu uggucgaaag gguaacgggu uaauauuccu guacggucca gguacuugcg gugacgcugg guugggcuuc

caacgcuucu ggguaggcug aguguucuug ucuggacauu caagcuuaua

ugacgcuuug ggguaggcug agcgggauuu ucguccuguu uaaggguuga

1761 aguccgggga gaguuguaau aacgag-aac cggaugaaag agugaugagc ucuccguuag gagaguucgg ccgaucucug

agccugggga gagccguaau ggcgagaacc auggugaagg ccugaauagc caucccuugu gggugguuug gcugugcccu

gag---cccg ugaaaaggga acuagcaagg auucuagaug uccguaccca gaaccgacac uggugccccu aggugaguau

ggaguccuug aaaagggagu ccuucuuggg auccuggauc gccguaccga gauccgacac uggugccccu agcugaguag

1921 ccuaaggcgu agcgggauga aucuagucga gggaagucgg caaauugguu ccguaacuuc gggagaagga gugccaguga

gcuaagg-ug uguuggggua accuggcuaa gggaaaucgg caaauuggcc ccguaacuuu gggagaaggg gugccag---

ucuuguuuaa auaugggauc gcuggucgca gugaccaggg agguccgacu guuuaauaca aacauagguc uuagcgagcc

---------c caugcggaug gcuggucgca gugacagggg gggcccgacu guuuaauaaa aacauagcuc cuagcuagcc

2081 ugaaaaggug uguacuaagg ccgacgccug cccagugcug guacgugaac cccgguucca accgggcgaa gcgccaguaa

cgugagggug uguacugggg gcgacaccug cccagugccg gcacgugaag cccugguuca acggggugaa gcgccgguaa

acggcggggg uaacuauaac ccucuuaagg uagcgaaauu ccuugucggg caaguuccga ccugcaugaa uggcguaacg

acggcggggg uaacuauaac ccucuuaagg uagcgaaaug ccuugccgga uaaguaccgg ccugcaugaa ugguugaacg

2241 agaccuccac uguccccgac uagaauccgg ugaaccuacc auuccggcgc aaaggccgga gacuuccagu gggaagcgaa

aggucccuac ugucccuagc caggaccuag ugaagcugcu guucuggugc acaagccaga gacucccagu gggaagcgaa

gaccccgugg agcuuuacug cagccugucg uuggggcaug guugugagug uacaguguag gugggagcca ucgaaacc--

gaccccguag agcuuuacug cagucugcug uuggggcuug gucaugggua ugcaguguag gugggaggcg ucgaugccau

4.4 Applications of Sequence Alignment and Examples 141

Table 4.6. (continued)

2401 uuuucgccag gaaaggugga ggcgauccug ggacaccacc cucucau--- --gaccaugu uccucacccu uuuaggggac

ggucgccagg cuguggugga gucggucaug agacaccacc uuccugugac ugugucucua accccauguu ugugggggac

accgguaggu gggcaguuug gcuggggcgg uacccuccua aaaaugcauc aggagggccc caaagguugg cucaagcggg

aucgguagau gggcaguuug gcuggggcgg cacgcgcuug aaauggua-u caagcgcgcc cuaaggucgg cucaggcggg

2561 ucaggacucc gcuguugagu guaagggcaa aagccagccu gacuuuguug ccaacaaaac gcaacgaaga ggcgaaagcc

acagagaucc gcuguagagu guaagggcau aagccggcuu gacugugcuc cuacuaguag ggggugcagg ugcgagagca

gggccuaacg a-accccugu gccucacuga ugggggccag ggaugacaaa aaagcuaccc cggggauaac agaguugucg

gggccuagcg aaccccagag uccucgucgg ugggggccug ggaugacaga aaagcuaccu cggggauaac uggguggucg

2721 cgggcaagag cccauaucga ccccgcggcu ugcuaccucg augucgguuu uucccauccu gggucugcag caggacccaa

caggcaagag cccauaucga cccugcggcu ugcuacuucg augucgguuc uuuccauccu gggugugcag cagcacccaa

ggguggggcu guucgcccau uaaaggggau caugagcugg guuuagaccg ucgugagaca gguugguugc uaucugcugg

gggugggguu guucgcccau uaaaggggaa cgugagcugg guuuagaccg ucgugagaca gguugguugc uaucuacugg

2881 auguguuagg cugucugagg gaaagguggc ucuaguacga gaggaacggg ccgucggcgc cucuagucga ucgguugucu

gagugugugg uugccugagg ggaagguggu uccaguacga gaggaacgga ccgucggcgc cucugguuua ccgguuaucc

gacaaggcac ugccgagcag ccacgcgc-c aagagauaag agcugaaagc aucuaagcuc gaaauucauc cugaaaauaa

gaguggguau ugccgggcgg cuacgcgcua ugauuauaaa ggcugaaggc aucuaagccu gagguuuucc cugaaaauag

3041 gacagccguu uccuucggga acgagaacuc ccguagaaga cggguuugau aggcuagggg uguacgcauc aagguucuuc

guggcuugug gacugcgggu agaagaccug uuuguugggg cgggggugug agcuucg--- -----aggcc uguuuugggc

cgagauguuc agcccgcuag uacuaacagu cucgagagau aauuuaggca u

cgaguuguuu agccugccgu uuccaagguu -uuuuguccc u--------- -

as follows:

k 123456789101112131415

 20220143392132113



(k) 0 20 22 42 43 47 50 53 62 64 65 68 70 71 72

k 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 2511 27112181110



(k) 75 77 82 83 84 0 3 10 11 23 24 32 33 43 53

in which L



+1) = L



is the sum of the virtual symbols in se-

quence A



,andL



+1) = L



is the sum of the virtual symbols in

sequence B



.Then



= n

+ L



= n



= n

+ L



It follows that the expanded mode of the sequences (A, B) has the follow-

ing form:

⎧

⎪

⎨

⎪

⎩

= {(121, 20), (190, 2), (296, 20), (344, 1), (524, 4), (585, 3), (646, 3),

(713, 9), (719, 2), (1038, 1), (1266, 3), (1440, 2), (1521, 1),

(1605, 1), (1661, 3), (2216, 2), (2263, 5), (2465, 1), (2797, 1)},

= {(0, 2), (1189, 7), (1411, 1), (1806, 1), (1864, 12),

(2395, 1), (2963, 8), (3008, 1), (3018, 10)} .

(4.41)

142 4 Super Pairwise Alignment

4. With the help of (4.41), we ﬁnd that the mutation mode of sequences

(A, B)isoftheform

(a,b)

=(H

⎧

⎪

⎨

⎪

⎩

(0, −2), (121, 20), (190, 2), (296, 20), (344, 1), (524, 4), (585, 3),

(646, 3), (713, 9), (719, 2), (1038, 1), (1189, −7), (1266, 3), (1411, −1),

(1440, 2), (1521, 1), (1605, 1), (1661, 3), (1806, −1), (1864, −12),

(2216, 2), (2263, 5), (2395

, −1), (2465, 1), (2797, 1), (2963, −8),

(3008, −1), (3018, −10) ,

(4.42)

in which type-III mutation occurs at position i

in sequence A if 

positive, and type-IV mutation occurs at position i

in sequence A if



is negative. Therefore, we obtain the mutation shifting function as in

Table 4.7.

Here the mutation mode of A from B is

(b,a)

⎧

⎪

⎨

⎪

⎩

(0, 2), (119, −20), (208, −2), (316, −20), (384, −1), (565, −4),

(630, −3), (694, −3), (764, −9), (779, −2), (1100, −1), (1252, 7),

(1322, 3), (1470, 1), (1498, −2), (1581, −1), (1666, −1), (1723, −3),

(1871, 1), (1928

, 12), (2268, −2), (2317, −5), (2454, 1), (2523, −1),

(2856, −1), (3023, 8), (3060, 1), (3069, 10) ,

(4.43)

where type-III mutation occurs at position i

in sequence B if 

is pos-

itive, and type-IV mutation occurs at position i

in sequence B if 

negative.

Table 4.7. The mutation shifting function

k 12345678910

0 121 190 296 344 524 585 646 713 719



−220220143392

a,b

0 −21820404145485160

k 11 12 13 14 15 16 17 18 19 20

1038 1189 1266 1411 1440 1521 1605 1661 1806 1864



1 −73−12113−1 −12

a,b

62 63 56 59 58 60 61 62 65 64

k 21 22 23 24 25 26 27 28 29 30

2216 2263 2395 2465 2797 2963 3008 3018



25−111−8 −1 −10

a,b

52 54 59 58 59 60 52 51 41

4.4 Applications of Sequence Alignment and Examples 143

Local Modiﬁcation Operations of Sequence Alignment

Sequence (A



) in Table 4.6 is the output of the SPA. This result is not the

minimum penalty alignment, but we can use local modiﬁcation operations to

reduce its penalty. The result after local modiﬁcation operations is listed in

Table 4.8.

Using Table 4.8, we ﬁnd that the overall penalty is reduced by 48. If we

denote the sequences after the local modiﬁcation operation from (A



)as



), then their similarity is

r(C



)=0.6690 +

3061

=0.6690 + 0.0157 = 0.6847.

Several calculations indicate that the similarity can be increased by 1–3% af-

ter the local modiﬁcation operation for the SPA. Therefore, we can implement

optimal alignment. The virtual symbols become dispersed after the local mod-

iﬁcation operation, so here, k



are increased, while the absolute value of



is decreased.

Estimation of the Parameters of Sequence Mutation

We make the following estimation of the parameters of the mutation structure

of (A, B):

1. Based on the result (A



), the probability of type-III or type-IV muta-

tions is:

⎧

⎪

⎨

⎪

⎩





2977

=0.0064 ,





2977

=0.0030 .

Then the average length of type-III or type-IV mutation and its parameter

of geometric distribution are:

=5.421 ,p

=0.2260 ,

=5.889 ,p

=0.1698 ,

respectively.

Basedontheresult(C



), we ﬁnd that the probability of type-III or

type-IV mutation increases slightly, but the average length of type-III or

type-IV mutation is reduced slightly (the parameter of geometric distri-

bution increases slightly). Therefore, the question of whether to base the

estimation on results (A



)oron(C



) should be analyzed further.

144 4 Super Pairwise Alignment

Table 4.8. Local modiﬁcation operations of the RNA sequences (A



)shownin

Table 4.6

Beginning Original result Result of local Reduced

position of alignment modiﬁcation operation penalty

1 uauc uauc 1

—cu –cu–

211 —aa aa— 2

aagc aagc

314 ugaga——– u–g–a–g—– 2

gcguaugggg gcguaugggg

326 ——————– aaag–cug–aag– 3

—–aaagcugaag ——————–

gccgggugugu gccgggugugu

gguguugaacuu gguguugaacuu

387 –ua ua– 2

uac uac

568 ——gua —gu–a– 3

cggugac cggugac

633 —-cu —cu– 1

gagua gagua

765 uu————–u —uu———u– 3

cuuugugcugug cuuugugcugug

782 —cg cg— 2

cggg cggg

1199 uaa uaa 2

–ua ua–

1329 gu—–g –gu–g– 3

uguggu uguggu

1509 —a a— 1

agg agg

1732 ag—–cc –ag–cc– 4

gaguccd gaguccd

1899 aaaua aaaua 2

–ccau ccau–

2290 –u u– 1

ug ug

2338 ——–gac gac——– 3

gacugugu gacugugu

2419 ucaggaggg ucaggaggg 4

–ucaagcgc ucaagcgc–

2532 –accccugug accccugug– 4

accccagagu accccagagu

2994 acgcau acgcau 3

—aggc aggc—

3049 uaauuuaggcauc uaauuuaggcauc 2

cu—————– ————–c–u–

4.4 Applications of Sequence Alignment and Examples 145

2. The statistical results for type-II mutation occurring in (A



)aregiven

as follows:

(

,

)1234

1 231144

2935

3521

(4.44)

where the ﬁgures in the square matrix indicate the number of type-II

mutations with mutation mode (

,

). The ﬁnal is result that a type-II

mutation occurs 68 times. Thus, the intensity of type-II mutation is 

68/2977 = 0.023.

Based on (4.44), we ﬁnd the joint probability distribution of (

∗

,

∗

)is:

i,j

1234

10.34328 0.16418 0.05970 0.05970

20.13433 0.04478 0.07463

30.07463 0.02985 0.01493

40.01493

(4.45)

where p

i,j

= P

{(

∗

,

∗

)=(i, j)}. Therefore, the average length of (

∗

,

∗

)

and their parameters of geometric distribution are:

=1.5075 ,p

=0.6634 ,

=1.6866 ,p

=0.5929 .

Utilizing (4.45), we calculate their mutual information as

I(

∗

,

∗



i=1



j=1

i,j

log



i,j



=0.0772 , (4.46)

where p



j=1

i,j

, q



i=1

i,j

. Since the value of I(

∗

,

∗

)issuﬃ-

ciently small in practice, we conclude that 

∗

,

∗

are independent random

variables.

3. Based on (A



) and the statistical result of type-II mutation, we ﬁnd

that the total error occurring in the region of type-II mutation is 162.

Therefore, the total error induced by type-I mutation is 1023 − 84 −53 −

162 = 724, where 84 is the error caused by the virtual symbols inserted

in sequence C, and 53 is the error caused by the virtual symbols inserted

in sequence D. Therefore, we get the intensity of type-I mutation: 

724/2977 = 0.2432.

In summary, we ﬁnd estimations for the parameters of 4 types of mutations

acting on sequences (A, B) as shown below:



0.24 0.02 0.006 0.003 0.663 0.593 0.226 0.170

(4.47)

146 4 Super Pairwise Alignment

Based on the above analysis, we ﬁnd that the mutation structures of gene se-

quences Mc.vanniel and Mb.tautotr agree with the stochastic mutation modes

presented in Chap. 2. However, the issue of the statistical independence of the

variables must still be addressed. These results oﬀer a reference for analyzing

the mutation and alignment of multiple sequences.

4.5 Exercises

Exercise 16. Choosing the Hamming matrix as the penalty matrix, write

down the computational program of the SPA, and do the following calcula-

tions:

1. Align the sequences given in Sect. 4.4.2.

2. For Sect. 4.4.2, compare the SPA with the dynamic programming algo-

rithm (introduced in Chap. 1) for the vital indices of alignment, such as

the similarity and CPU time.

Exercise 17. Use the SPA to align the sequences produced by the simulation

method in Chap. 2, and consider the following problems:

1. Analyze the relationship between the length of the sequences and the CPU

time using the SPA.

2. Compare the similarity between the aligned sequence obtained from the

SPA and that from using the dynamic programming algorithm, and give

the statistics of the diﬀerence of similarity, on average.

Exercise 18. Let (A, B) be the sequences given in Table 4.5, and let (A



)

be the aligned sequences given in Table 4.6. Analyze and calculate the follow-

ing:

1. In (4.21), one kind of modulus structure of (A



) is given. With a similar

argument, give two other forms of the modulus structure of (A



2. Modify the results given in Table 4.6 using the local modiﬁcation operation

given in Table 4.8, such that the ﬁnal result is (A



). Write down the

representation of (A



3. Compare the similarity between sequences (A



) and the sequences

obtained by a dynamic programming algorithm.

Exercise 19. State the diﬀerences between sequential decision and self-adap-

tive regression decision, and write a program for the improved SPA using

self-adaptive regression decision.

Exercise 20. According to the various types of local modiﬁcations given in

Table 4.8, give a computational program for local modiﬁcation operation.

4.5 Exercises 147

Hints

For the SPA for pairwise alignment, it is better to write a program that

includes the steps presented in Sect. 4.2. If you have diﬃculties, you may use

the algorithm provided on our Web site [99], and then try programming by

yourself.