BiBiServ Logo
Attention:
Due to technical maintenance some tools will not be available.
See maintenance description for more information.
BiBiServ - Bielefeld University Bioinformatic Service
Tools
Education
Administration
Tools
Genome Comparison
Gecko
REPuter
...more
Alignments
e2g
PoSSuMsearch
...more
Primer Design
GeneFisher
RNA Studio
RNAcast
RNAshapes
...more
Evolutionary Relationship
ROSE
SplitsTree
...more
Others
XenDB
PREdictor
...more

OMA Testreihe mit Daten der BAliBASE

OMA Testreihe mit Daten der BAliBASE

Torsten Will
Technische Fakultät und
Mathematische Fakultät
22. Mai 1998

Zusammenfassung

Es wurde eine spezielle Version von OMA implementiert, die fuer einen Vergleich mit MSA gedacht ist. Das Programm heisst testMsa/1 und hat  gegenueber MSA den algorithmischen Zusatz, GDUS (Goal Directed Unidirectional Search, A*-Algorithmus) implementiert zu haben.

Die BAliBASE ist eine Sammlung von Sequenzdaten fuer den Vergleich verschiedener Alignmentprogramme. Eine geeignete Auswahl an Datensaetzen wurde getestet. [http://www-igbmc.u-strasbg.fr/BioInfo/BAliBASE/index.html].

 (Zurück)

Einleitung

Da die Sequenzdaten in einem Format Namens "RSF" vorliegen, wurden sie mit einem awk-Scprip ins Fasta-Format konvertiert [nawk -f bali/rsf2fasta.awk].

testMsa/1 versucht das Verhalten von Msa 2.1 auf folgende Weise nachzuahmen:

  • MSA wird mit -g und -b aufgerufen: "gleiche Gewichtung" und "TermGaps zaehlen". Das heuristische Alignment von MSA liefert die obere Schranke fuer die OMA Algorithmen.
  • GDUS ist eingeschaltet, SmartPrio wird verwendet
  • Eine Segmentierung oder Iteration ueber die Segmentlaengen findet nicht statt

Sowohl bei MSA 2.1, als auch bei testMsa/1 sind allerlei Zaehlungen und Messungen eingefuegt worden um die Performance messen zu koennen.

Sequenzdaten

Alle Tests wurden mit der Kostenmatrix dayhoff.cost durchgefuehrt.

Die verwendeten Sequenzdaten haben folgende Merkmale:

  • Identity: Average percent identiy
  Anzahl Laengen Identity Description
ref1/test1       short sequences
group 1       <25% identity
1aboA 5 49-80 15 SH3
1idy 5 49-58 14 myb dna-binding domain
1r69 4 63-78 13 repressor
1tvxA 4 51-69 18 pertussis toxin
1ubi 4 76-94 18 ubiquitin
1wit 5 89-106 17 twitchin
2trx 4 85-99 17 thioredoxin
group 2       <20-40% identity
1aab 4 67-79 30 high mobility group protein
1fjlA 6 58-70 28 homeodomain
1hfh 5 116-132 31 factor h
1hpi 4 70-81 33 high-potential iron-sulfur protein
1csy 5 100-104 30 SH2
1pfc 5 108-117 28 immunoglobulin PFc fragment
1tgxA 4 57-64 31 cardiotoxin
1ycc 4 90-116 29 cytochrome e
3cyr 4 95-109 31 cytochrome c3
451c 5 70-87 27 cytochrome c
group 3       >35% identity
1aho 5 61-67 44 toxin II
1csp 5 66-70 51 cold shock protein
1dox 4 91-96 46 ferredoxin [2fe-2s]
1fkj 5 98-110 44 immunophilin
1fmb 4 98-104 49 hiv-1 protease
1krn 5 66-82 45 serine protease
1plc 5 88-99 46 plastocyanin
2fxb 5 55-63 51 ferredoxin
2mhr 5 110-118 45 hemerythrin
9rnt 5 96-103 57 ribonuclease
ref1/test2       medium length sequences
group 4       medium, <25% identity
1bbt3 5 149-192 13 foot-and-mouth disease virus
1sbp 5 224-263 19 sulfate binding protein
1havA 5 136-199 15 hepatitis proteinase
1uky 4 186-220 15 uridylate kinase
2hsdA 4 225-262 19 3a, 20b-hydroxysteroid dehydrogenase
2pia 4 223-287 20 phtalate reductase
3grs 4 201-237 14 glutathione reductase
kinase 5 263-276 20 protein kinase
group 5       20-40% identity
1ad2 4 203-213 30 ribosomal protein l1
1aym3 4 219-244 32 rhinovirus 16 coat protein
1gdoA 4 234-265 30 glucosamine 6-phosphate synthase
1ldg 4 303-315 27 lactate dehydrogenase
1mrj 4 247-266 33 alpha tricosanthin
1pgtA 4 199-212 26 glutathione
1pii 4 247-259 32 anthranilate isomerase
1ton 5 224-244 30 tonin
2cba 5 237-259 26 anhydrase
group 6       medium, >35% identity
1amk 5 242-254 49 triose phosphate isomerase
1ar5A 4 192-203 42 superoxide dismutase
1ezm 5 297-308 60 elastase
1led 4 232-243 43 lectin
1ppn 5 212-220 46 papain
1pysA 4 237-266 44 phenylalanyl-trna synthetase
1thm 4 269-279 49 serine protease
1tis 5 263-295 50 thymidylate sythase
1zin 4 206-216 42 adenylate kinase
5ptp 5 222-245 43 serine protease
ref1/test3       long sequences
group 7       <25% identity
1ajsA 4 358-387 15 aminotransferase
1cpt 4 378-434 20 cytochrome p450
1lvl 4 401-449 19 dihydrolipoamide dehydrogenase
1pamA 5 435-572 18 cyclodextrin
1ped 3 327-374 24 alcohol dehydrogenase
2myr 4 340-474 16 myrosinase
4enl 3 333-421 20 enolase
gal4 5 335-395 14 gal4
group 8       20%<40% identity
1ac5 4 421-483 29 carboxypeptidase
1adj 4 404-418 35 histidyl-trna synthetase
1bgl 4 ! 938-993 31 b-galactoxidase
1dlc 4 ! 567-590 32 endotoxin
1eft 4 334-405 30 eftu
1fieA 4 ! 664-675 34 coagulation factor xiii
1gowA 4 451-481 31 beta_glycosidase
1pkm 4 434-449 34 pyruvate kinase
1sesA 5 417-442 33 seryl-tRNA synthetase
2ack 5 452-482 28 acetylcholinesterase
arp 5 380-418 29 arp
glg 5 438-486 31 glutamyl-trna synthetase
group 9       >35% identity
1ad3 4 424-447 47 aldehyde dehydrogenase
1gpb 5 ! 796-828 47 glycogen phosphorylase b
1gtr 5 419-436 42 glutaminyl-tRNA synthetase
1lcf 6 ! 662-691 49 lactoferrin
1rthA 5 ! 526-541 42 reverse transcriptase
1taq 5 ! 806-928 40 taq DNA polymerase
3pmg 4 ! 540-567 51 phosphoglucomutase
actin 5 379-395 45 actin
Tabelle 1:
Sequenzen

Testreihe 1 mit testMsa

  • cost: Kosten des berechnet Alignments. "=" heisst das das Programm den gleichen Wert lieferte.
  • Objects: Anzahl der konstruierten (OMA-Library) Objekte insgesamt
  • Edge: Anzahl der konstruierten Edge-Objekte
  • reins E: Durch die Verwendung von GDUS mehrfach in die Queue eingefuegte Edges.
  • Vertex: Anzahl der konstruierten Vertex-Objekte
  • face invalid: Anzahl der mindestens einmal besuchten Gitterpunkte, die ausserhalb des face gueltigen Bereichs liegen und fuer die daher kein Vertex kreiert wurde.
  • time real/user: mit time angezeigte Zeit in [s]
  • mem[8kb]: Maximal angeforderter Speicher in 8kb-Pages
  • htX: Performancemessungen bei den Hashtables, die an zwei Stellen im Programm verwendet werden; Q steht fuer die PriorityQueue und T fuer den Trie
    • gets/puts: Anzahl der get/put-Operationen. Die angegebenen Werte sind ohne die benoetigten Operationen waehrend Rehashings angegeben.
    • probes: Es wird open adressing verwendet. Das Verhaeltnis von "probes" zu "gets+puts" ist ein Mass fuer die Performance.
Der verwendete Hashfunktion ist /1.0 aus Tabelle 2. Einige Werte konnte ich noch nicht messen: Mit "length" gekennzeichnete Messungen stiessen an die Grenze von 500 Zeichen pro Sequenz von MSA, mit "time" markierte Werte lieferten nach 10 Stunden noch kein Alignment und wurden abgebrochen.
  cost Objects Edge reins E Vertex face inv time user mem[8kb] htQ gets htQ puts htQ probes htQ perf htT gets htT puts htT probes htT perf
ref1/test1                                
group 1                                
1aboA 10698 2144840 1950 739 3925 148764 117303 360.904 24621 13077622 1950739 28430712 1.89 88026176 309968 120159878 1.36
1idy 9508 1475626 1330 745 1918 98784 69232 360.496 13545 13316891 1330745 24503729 1.67 88824017 212789 113363299 1.27
1r69 7294 298670 255 695 1016 32475 12909 29.326 3401 1386362 255695 2680809 1.63 6446342 54889 7717538 1.19
1tvxA 6538 593490 528 326 2658 54392 20719 89.513 5853 4322804 528326 8589767 1.77 19270652 84993 24708104 1.28
1ubi 8631 174504 146 727 774 22927 18765 23.657 2068 756006 146727 1205554 1.34 6272368 45397 7413458 1.17
1wit 16517 740189 660 803 1518 50217 75494 146.831 7821 5432473 660803 10331802 1.70 40161175 152696 51695053 1.28
2trx 9293 74449 58 871 223 9686 8800 6.806 1535 276525 58871 367917 1.10 1702167 23128 1869827 1.08
group 2                                
1aab 7061 7450 3 515 12 1370 1803 0.706 982 6797 3515 10425 1.01 70795 4701 76871 1.02
1fjlA 15965 26764 8 040 74 4675 11494 2.916 1351 12775 8040 21129 1.02 723850 27876 884678 1.18
1hfh
1hpi 6870 11731 6 654 58 2168 2442 1.186 1013 13650 6654 20621 1.02 142347 6476 151424 1.02
1csy
1pfc 17708 270836 235 150 959 17332 28333 38.170 4469 1491398 235150 2867562 1.66 10233866 61531 13031308 1.27
1tgxA 5695 29980 22 589 137 3693 4322 2.080 1053 78721 22589 105411 1.04 455418 10832 489026 1.05
1ycc 10548 50054 39 391 318 6032 13777 6.593 1488 245696 39391 305116 1.07 1873768 22998 2086735 1.10
3cyr 9888 32538 23 712 132 3798 5877 4.353 1394 126840 23712 156837 1.04 1091779 13297 1145960 1.04
451c 13380 374615 308 611 870 29798 59329 72.889 4243 2393267 308611 4287587 1.59 23821899 123485 33500617 1.40
group 3                                
1aho 9807 28724 19 615 29 2446 9083 4.115 1189 101955 19615 125274 1.03 1486757 16664 1574228 1.05
1csp 9910 5249 635 1 553 3143 0.781 1080 825 635 1464 1.00 64567 6153 72756 1.03
1dox 8748 21231 15 471 138 2808 2752 1.564 1252 38163 15471 55164 1.03 211800 7226 224095 1.02
1fkj 15809 11021 2 499 9 1153 6943 1.712 1595 5256 2499 7841 1.01 209925 13149 237664 1.07
1fmb 8804 3274 178 2 352 1594 0.840 1180 190 178 368 1.00 16522 3326 20404 1.03
1krn 11409 6331 339 6 1168 3552 1.018 1202 395 339 734 1.00 71336 7736 83452 1.06
1plc 14195 10522 2 646 25 1985 7389 1.657 1447 4398 2646 7079 1.00 219763 13137 246285 1.06
2fxb 8154 3380 145 0 170 1921 0.526 967 145 145 290 1.00 20371 3760 24745 1.03
2mhr 16687 7005 200 0 695 3847 1.723 1764 211 200 411 1.00 47618 8116 59234 1.06
9rnt 14475 8564 2 050 25 970 4855 1.533 1528 3412 2050 5495 1.01 108853 9125 122830 1.04
  cost Objects Edge reins E Vertex face inv time user mem[8kb] htQ gets htQ puts htQ probes htQ perf htT gets htT puts htT probes htT perf
ref1/test2                                
group 4                                
1bbt3
1sbp
1havA
1uky 21197 625782 560 494 1296 48905 44797 157.923 7258 6790931 560494 13409275 1.82 34067676 107486 50716981 1.48
2hsdA
2pia
3grs
kinase
group 5                                
1ad2 19714 83621 66 445 295 9573 8437 16.400 3247 345116 66445 460802 1.12 2197242 22965 2316066 1.04
1aym3 22031 319178 271 169 760 32300 20236 45.400 5746 1785675 271169 3359253 1.63 8365747 65285 10526217 1.25
1gdoA 24082 1977207 1771 393 3363 173264 60770 366.468 17920 16080402 1771393 34837594 1.95 70306125 263456 94703217 1.34
1ldg 29939 80503 57 197 133 11358 9429 11.191 5762 193010 57197 276672 1.11 1163272 28851 1336951 1.12
1mrj 24157 227222 191 528 792 22836 21976 33.532 5084 1437302 191528 2462525 1.51 7312664 54431 9098148 1.23
1pgtA 20160 180527 148 277 266 21058 14742 19.704 3858 796269 148277 1243809 1.32 4110727 44344 4925799 1.19
1pii 24347 230232 184 942 1100 25785 22553 24.022 5269 846078 184942 1562508 1.52 4513968 64661 6014402 1.31
1ton
2cba
group 6                                
1amk 36659 16711 2 190 8 1508 9692 12.391 5642 2992 2190 5219 1.01 152872 19001 194521 1.13
1ar5A 17722 18485 10 120 58 2588 5980 4.222 2670 23812 10120 34716 1.02 253517 11799 277522 1.05
1ezm 43746 19446 1 165 3 1289 12794 16.181 8023 1578 1165 2780 1.01 186243 24767 251331 1.19
1led 21788 97438 75 824 328 11246 12850 11.795 3956 359979 75824 499221 1.15 2063621 31459 2347656 1.12
1ppn 31731 39987 21 585 40 3737 15684 7.988 4649 74810 21585 100455 1.04 914736 29506 1095554 1.16
1pysA 22586 19500 8 927 51 2562 8232 5.941 3788 23631 8927 33561 1.03 426427 15626 480059 1.09
1thm 24978 8594 779 13 1213 4736 5.649 4295 898 779 1691 1.01 55837 9096 68582 1.06
1tis 41462 80764 42 793 216 7320 34077 14.774 7602 135588 42793 199920 1.12 2084195 66148 3321861 1.54
1zin 19220 10112 2 663 18 1489 4115 3.715 2895 4355 2663 7100 1.01 85544 8844 99559 1.05
5ptp
  cost Objects Edge reins E Vertex face inv time user mem[8kb] htQ gets htQ puts htQ probes htQ perf htT gets htT puts htT probes htT perf
ref1/test3                                
group 7                                
1ajsA time
1cpt 39820 1707144 1542123 6690 143872 141188 509.137 19760 17905055 1542123 40386713 2.08 90166660 301275 139563312 1.54
1lvl 44105 10065257 9206793 40400 783887 527445 4770.050 84451 112820059 9206793 1003499453 8.22 536184611 1380609 995167170 1.85
1pamA length
1ped 17900 554515 465455 4203 78797 12623 71.263 8232 2713449 465455 6679621 2.10 8755744 99479 12907500 1.46
2myr time
4enl 18909 508615 414925 4796 74070 31947 56.287 6988 2395779 414925 5954798 2.12 8431323 123349 14668792 1.71
gal4 time
group 8                                
1ac5 43325 12661570 11572912 35242 930671 326163 5539.512 94990 145053624 11572912 641437356 4.10 637075264 1409320 983707187 1.54
1adj 38036 53591 33868 151 7548 14667 22.063 9026 127032 33868 178196 1.11 1044843 29282 1227440 1.14
1bgl length
1dlc length
1eft 36601 478189 415507 3161 46352 65339 124.816 10640 3941152 415507 8367253 1.92 22220528 123318 34263013 1.53
1fieA length
1gowA 45321 7989250 7130411 18750 649039 395168 2763.348 87756 76301919 7130411 467045004 5.60 367702955 1248212 603141002 1.63
1pkm 42081 1601916 1426103 4571 145487 96984 435.252 21581 13495612 1426103 28524885 1.91 68914767 267338 96899014 1.40
1sesA 67140 2740599 2429681 2351 166607 259493 1197.802 37572 33561138 2429681 66369316 1.84 239093763 561607 332894481 1.39
2ack time
arp 64154 19295331 17914223 27894 938908 1227660 13580.159 175316 316344103 17914223 1135143681 3.40 2112538074 2600580 >int ?
glg time
group 9                                
1ad3 39209 33130 16045 77 4147 11697 25.367 9865 72793 16045 93281 1.05 767663 23380 852820 1.08
1gpb length
1gtr 64190 2767800 2525731 1850 153932 225415 1257.724 37566 38504476 2525731 75716540 1.85 248082043 458672 349748718 1.41
1lcf length
1rthA length
1taq length
3pmg length
actin 56938 191790 141304 462 17152 54692 60.956 13508 1210375 141304 1725480 1.28 13245718 97234 17260881 1.29
  cost Objects Edge reins E Vertex face inv time user mem[8kb] htQ gets htQ puts htQ probes htQ perf htT gets htT puts htT probes htT perf
Tabelle 2:
Erster Datensatz mit OMA

Testreihe 1 mit MSA

Mit "@" markierte Wert lieferten kein Alignment, weil MSA mit einem "Segmentation fault" abbrach!

  cost lower delta maxd Vertices Edges time
ref1/test1              
group 1              
1aboA 10 708 10 438 270 350 107 805 2099 463 199.2
1idy 9 508 9 357 151 237 57 511 1097 732 89.0
1r69 7 308 7 175 133 154 24 978 250 876 7.9
1tvxA 6 538 6 391 147 212 41 236 480 409 17.7
1ubi 8 631 8 507 124 150 12 024 102 247 2.8
1wit 16 517 16 332 185 299 14 940 200 479 10.9
2trx 9 293 9 159 134 178 7 412 67 153 1.9
group 2              
1aab 7 061 7 016 45 105 661 3 763 0.1
1fjlA @            
1hfh 19 208 19 084 124 209 1 975 16 280 0.9
1hpi 6 870 6 833 37 111 1 481 11 952 0.3
1csy @            
1pfc 17 710 17 578 132 245 6 742 112 133 7.6
1tgxA 5 695 5 621 74 159 1 714 10 809 0.3
1ycc 10 548 10 418 130 176 3 055 18 612 0.6
3cyr 9 888 9 800 88 120 2 335 19 658 0.6
451c 13 380 13 143 237 280 10 205 141 333 8.8
group 3              
1aho 9 807 9 677 130 203 900 7 684 0.4
1csp 9 910 9 886 24 150 248 932 0.1
1dox 8 748 8 709 39 113 2 307 19 517 0.6
1fkj 15 809 15 720 89 199 547 2 288 0.3
1fmb 8 804 8 784 20 95 227 445 0.1
1krn 11 409 11 376 33 150 412 1 748 0.2
1plc 14 195 14 122 73 177 1 195 7 047 0.4
2fxb 8 154 8 149 5 150 129 271 0.1
2mhr 16 687 16 648 39 150 219 450 0.3
9rnt 14 475 14 439 36 152 429 2 038 0.3
               
ref1/test2
group 4
1bbt3
1sbp
1havA
1uky
2hsdA
2pia
3grs
kinase
group 5
1ad2
1aym3
1gdoA
1ldg
1mrj
1pgtA
1pii
1ton
2cba
group 6
1amk
1ar5A
1ezm
1led
1ppn
1pysA
1thm
1tis
1zin
5ptp
 
ref1/test3
group 7
1ajsA
1cpt
1lvl
1pamA
1ped
2myr
4enl
gal4
group 8
1ac5
1adj
1bgl
1dlc
1eft
1fieA
1gowA
1pkm
1sesA
2ack
arp
glg
group 9
1ad3
1gpb
1gtr
1lcf
1rthA
1taq
3pmg
actin
 
Tabelle 3:
Erster Datensatz mit MSA

Literatur

 
Welcome
References
Download
Contact
Tue Dec 20 16:59:42 2005