57:. The notion of a gap in an alignment is important in many biological applications, since the insertions or deletions comprise an entire sub-sequence and often occur from a single mutational event. Furthermore, single mutational events can create gaps of different sizes. Therefore, when scoring, the gaps need to be scored as a whole when aligning two sequences of DNA. Considering multiple gaps in a sequence as a larger single gap will reduce the assignment of a high cost to the mutations. For instance, two protein sequences may be relatively similar but differ at certain intervals as one protein may have a different subunit compared to the other. Representing these differing sub-sequences as gaps will allow us to treat these cases as “good matches” even though there are long consecutive runs with indel operations in the sequence. Therefore, using a good gap penalty model will avoid low scores in alignments and improve the chances of finding a true alignment. In genetic sequence alignments, gaps are represented as dashes(-) on a protein/DNA sequence alignment.
308:. This introduces new terms, A is known as the gap opening penalty, B the gap extension penalty and L the length of the gap. Gap opening refers to the cost required to open a gap of any length, and gap extension the cost to extend the length of an existing gap by 1. Often it is unclear as to what the values A and B should be as it differs according to purpose. In general, if the interest is to find closely related matches (e.g. removal of vector sequence during genome sequencing), a higher gap penalty should be used to reduce gap openings. On the other hand, gap penalty should be lowered when interested in finding a more distant match. The relationship between A and B also have an effect on gap size. If the size of the gap is important, a small A and large B (more costly to extend a gap) is used and vice versa. Only the ratio A/B is important, as multiplying both by the same positive constant
182:
efficient over a relatively broad range of evolutionary change. The BLOSUM-62 matrix is one of the best substitution matrices for detecting weak protein similarities. BLOSUM matrices with high numbers are designed for comparing closely related sequences, while those with low numbers are designed for comparing distant related sequences. For example, BLOSUM-80 is used for alignments that are more similar in sequence, and BLOSUM-45 is used for alignments that have diverged from each other. For particularly long and weak alignments, the BLOSUM-45 matrix may provide the best results. Short alignments are more easily detected using a matrix with a higher "relative entropy" than that of BLOSUM-62. The BLOSUM series does not include any matrices with relative entropies suitable for the shortest queries.
568:
gap penalties, such as the affine gap penalty, are often implemented independent of the amino acid types in the inserted or deleted fragment or at the broken ends, despite evidence that specific residue types are preferred in gap regions. Finally, alignment of sequences implies alignment of the corresponding structures, but the relationships between structural features of gaps in proteins and their corresponding sequences are only imperfectly known. Because of this incorporating structural information into gap penalties is difficult to do. Some algorithms use predicted or actual structural information to bias the placement of gaps. However, only a minority of sequences have known structures, and most alignment problems involve sequences of unknown secondary and tertiary structure.
502:
substitution matrices to measure the similarity of amino acid pairs, profile–profile alignment methods require a profile-based scoring function to measure the similarity of profile vector pairs. Profile-profile alignments employ gap penalty functions. The gap information is usually used in the form of indel frequency profiles, which is more specific for the sequences to be aligned. ClustalW and MAFFT adopted this kind of gap penalty determination for their multiple sequence alignments. Alignment accuracies can be improved using this model, especially for proteins with low sequence identity. Some profile–profile alignment algorithms also run the secondary structure information as one term in their scoring functions, which improves alignment accuracy.
222:
135:
167:
492:
and was proposed as studies had shown the distribution of indel sizes obey a power law. Another proposed issue with the use of affine gaps is the favoritism of aligning sequences with shorter gaps. Logarithmic gap penalty was invented to modify the affine gap so that long gaps are desirable. However,
151:
algorithm. When comparing proteins, one uses a similarity matrix which assigns a score to each possible residue pair. The score should be positive for similar residues and negative for dissimilar residue pairs. Gaps are usually penalized using a linear gap function that assigns an initial penalty for
119:
The use of semi-global alignment exists to find a particular match within a large sequence. An example includes seeking promoters within a DNA sequence. Unlike global alignment, it compromises of no end gaps in one or both sequences. If the end gaps are penalized in one sequence 1 but not in sequence
501:
Profile–profile alignment algorithms are powerful tools for detecting protein homology relationships with improved alignment accuracy. Profile-profile alignments are based on the statistical indel frequency profiles from multiple sequence alignments generated by PSI-BLAST searches. Rather than using
20:
is a method of scoring alignments of two or more sequences. When aligning sequences, introducing gaps in the sequences can allow an alignment algorithm to match more terms than a gap-less alignment can. However, minimizing gaps in an alignment is important to create a useful alignment. Too many gaps
181:
are used for sequence alignment of proteins. A Substitution matrix assigns a score for aligning any possible pair of residues. In general, different substitution matrices are tailored to detecting similarities among sequences that are diverged by differing degrees. A single matrix may be reasonably
567:
There are a few challenges when it comes to working with gaps. When working with popular algorithms there seems to be little theoretical basis for the form of the gap penalty functions. Consequently, for any alignment situation gap placement must be empirically determined. Also, pairwise alignment
142:
A local sequence alignment matches a contiguous sub-section of one sequence with a contiguous sub-section of another. The Smith-Waterman algorithm is motivated by giving scores for matches and mismatches. Matches increase the overall score of an alignment whereas mismatches decrease the score. A
249:
Compared to the constant gap penalty, the linear gap penalty takes into account the length (L) of each insertion/deletion in the gap. Therefore, if the penalty for each inserted/deleted element is B and the length of the gap L; the total gap penalty would be the product of the two BL. This method
204:
can have severe biological consequences by causing mutations in the DNA strand that could result in the inactivation or over activation of the target protein. For example, if a one or two nucleotide indel occurs in a coding sequence the result will be a shift in the reading frame, or a
85:- Gap penalties allow algorithms to detect where sections of a document are plagiarized by placing gaps in original sections and matching what is identical. The gap penalty for a certain document quantifies how much of a given document is probably original or plagiarized.
105:
A global alignment performs an end-to-end alignment of the query sequence with the reference sequence. Ideally, this alignment technique is most suitable for closely related sequences of similar lengths. The
Needleman-Wunsch algorithm is a
21:
can cause an alignment to become meaningless. Gap penalties are used to adjust alignment scores based on the number and length of gaps. The five main types of gap penalties are constant, linear, affine, convex, and profile-based.
200:, the cellular replication machinery is prone to making two types of errors while duplicating the DNA. These two replication errors are insertions and deletions of single DNA bases from the DNA strand (indels).
110:
technique used to conduct global alignment. Essentially, the algorithm divides the problem into a set of sub-problems, then uses the results of the sub-problems to reconstruct a solution to the original query.
234:
This is the simplest type of gap penalty: a fixed negative score is given to every gap, regardless of its length. This encourages the algorithm to make fewer, larger, gaps leaving larger contiguous sections.
520:
often involves sequences of varying lengths. It is important to pick a model that would efficiently run at a known input size. The time taken to run the algorithm is known as the time complexity.
213:. However, not all indels are frameshift mutations. If indels occur in trinucleotides, the result is an extension of the protein sequence that may also have implications on protein function.
1277:
Henneke CM (1989). "A multiple sequence alignment algorithm for homologous proteins using secondary structure information and optionally keying alignments to functionally important sites".
429:
241:
Aligning two short DNA sequences, with '-' depicting a gap of one base pair. If each match was worth 1 point and the whole gap -1, the total score: 7 − 1 = 6.
264:
The most widely used gap penalty function is the affine gap penalty. The affine gap penalty combines the components in both the constant and linear gap penalty, taking the form
306:
490:
225:
This graph shows the difference between types of gap penalties. The exact numbers will change for different applications but this shows the relative shape of each function.
439:
Using the affine gap penalty requires the assigning of fixed penalty values for both opening and extending a gap. This can be too rigid for use in a biological context.
993:
Wang C, Yan RX, Wang XF, Si JN, Zhang Z (12 October 2011). "Comparison of linear gap penalties and profile-based variable gap penalties in profile-profile alignments".
637:
346:
326:
256:
Unlike constant gap penalty, the size of the gap is considered. With a match with score 1 and each gap -1, the score here is (7 − 3 = 4).
209:
that may render the protein inactive. The biological consequences of indels are often deleterious and are frequently associated with pathologies such as
147:
finds an alignment with the highest score by considering only alignments that score positives and picking the best one from those. The algorithm is a
1244:"A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given"
692:
1358:
914:
861:
656:
1037:
Wrabl JO, Grishin NV (1 January 2004). "Gaps in structurally similar proteins: towards improvement of multiple sequence alignment".
493:
in contrast to this, it has been found that using logarithmatic models had produced poor alignments when compared to affine models.
716:
Vingron, M.; Waterman, M. S. (1994). "Sequence alignment and penalty choice. Review of concepts, case studies and implications".
1155:
Vingron M, Waterman MS (1994). "Sequence alignment and penalty choice. Review of concepts, case studies and implications".
129:
613:
100:
54:
50:
351:
631:
517:
221:
788:
Garcia-Diaz, Miguel (2006). "Mechanism of a genetic glissando: structural biology of indel mutations".
34:
267:
445:
206:
174:
161:
148:
107:
38:
1143:
1062:
1337:
1294:
1265:
1230:
1201:
1172:
1135:
1106:
1054:
1010:
966:
910:
857:
805:
733:
1327:
1319:
1286:
1255:
1222:
1193:
1164:
1127:
1096:
1046:
1002:
956:
946:
797:
725:
1260:
1243:
762:
667:
511:
197:
144:
79:
to a misspelled word. Gaps can indicate a missing letter in the incorrectly spelled word.
152:
a gap opening, and an additional penalty for gap extensions, increasing the gap length.
143:
good alignment then has a positive score and a poor alignment has a negative score. The
1006:
961:
934:
331:
311:
1332:
1307:
1168:
1101:
1084:
823:
729:
69:- computes the minimal difference between two files similarly to plagiarism detection.
1352:
1290:
1226:
1197:
1147:
76:
45:. Insertions or deletions can occur due to single mutations, unbalanced crossover in
1066:
33:- In bioinformatics, gaps are used to account for genetic mutations occurring from
134:
847:
845:
801:
612:
Carroll, Ridge, Clement, Snell, Hyrum , Perry, Mark, Quinn (January 1, 2007).
1323:
587:
951:
1058:
1014:
970:
809:
250:
favors shorter gaps, with total score decreasing with each additional gap.
1341:
1298:
1269:
1234:
1205:
1184:
Panjukov VV (1993). "Finding steady alignments: similarity and distance".
1176:
1139:
1110:
737:
431:
which does not change the relative penalty between different alignments.
120:
2, it produces an alignment that contains sequence 2 within sequence 1.
75:- Gap penalties can help find correctly spelled words with the shortest
1131:
1050:
46:
1213:
Alexandrov NN (1992). "Local multiple alignment by consensus matrix".
877:
210:
201:
178:
166:
1118:
Taylor WR (1996). "A non-local gap-penalty for profile alignment".
220:
191:
165:
133:
618:
International
Journal of Bioinformatics Research and Applications
1308:"On the statistical assessment of similarities in DNA sequences"
63:
878:"Global Alignment with Scoring Matrix and Affine Gap Penalty"
907:
1085:"Multiple sequence threading: conditional gap placement"
448:
354:
334:
314:
270:
935:"Logarithmic gap costs decrease alignment accuracy"
582:
580:
522:
484:
423:
340:
320:
300:
783:
781:
779:
614:"Effects of Gap Open and Gap Extension Penalties"
524:Time complexities for various gap penalty models
1032:
1030:
1028:
1026:
1024:
988:
986:
984:
982:
980:
8:
636:: CS1 maint: multiple names: authors list (
41:in the sequence, sometimes referred to as
1331:
1259:
1100:
960:
950:
447:
353:
333:
313:
269:
852:Hodgman C, French A, Westhead D (2009).
1306:Reich JG, Drabsch H, Daumler A (1984).
576:
757:
755:
753:
751:
749:
747:
629:
424:{\displaystyle kA+kB(L-1)=k(A+B(L-1))}
138:Example of Protein Sequence Alignment
1261:10.1093/oxfordjournals.molbev.a040577
928:
926:
900:
898:
856:. Garland Science. pp. 143–144.
7:
854:BIOS Instant Notes in Bioinformatics
651:
649:
647:
442:The logarithmic gap takes the form
1007:10.1016/j.compbiolchem.2011.07.006
14:
824:"Glossary - Constant Gap Penalty"
253:ATTGACCTGA || ||||| AT---CCTGA
238:ATTGACCTGA || ||||| AT---CCTGA
664:Algorithms for Molecular Biology
933:Cartwright, Reed (2006-12-05).
328:will increase all penalties by
1291:10.1093/bioinformatics/5.2.141
1227:10.1093/bioinformatics/8.4.339
1198:10.1093/bioinformatics/9.3.285
790:Trends in Biochemical Sciences
458:
452:
418:
415:
403:
391:
382:
370:
301:{\displaystyle A+B\cdot (L-1)}
295:
283:
1:
1169:10.1016/S0022-2836(05)80006-3
1102:10.1016/S1359-0278(97)00061-8
909:. CRC Press. pp. 42–47.
763:"BLAST substitution matrices"
730:10.1016/S0022-2836(05)80006-3
691:Lesk, Arthur M (2013-07-26).
485:{\displaystyle G(L)=A+C\ln L}
1083:Taylor WR, Munro RE (1997).
830:. Rosalind Team. 12 Aug 2014
718:Journal of Molecular Biology
666:. 2006-01-01. Archived from
1359:Computational phylogenetics
884:. Rosalind Team. 2012-07-02
506:Comparing time complexities
90:Bioinformatics applications
1375:
802:10.1016/j.tibs.2006.02.004
509:
189:
159:
127:
101:Needleman-Wunsch algorithm
98:
31:Genetic sequence alignment
55:chromosomal translocation
51:slipped strand mispairing
516:The use of alignment in
130:Smith–Waterman algorithm
952:10.1186/1471-2105-7-527
905:Sung, Wing-Kin (2011).
697:Encyclopædia Britannica
1324:10.1093/nar/12.13.5529
486:
425:
342:
322:
302:
226:
171:
139:
537:Constant gap penalty
518:computational biology
510:Further information:
487:
426:
343:
323:
303:
224:
175:Substitution matrices
169:
137:
115:Semi-global alignment
446:
352:
332:
312:
268:
83:Plagiarism detection
553:Convex gap penalty
545:Affine gap penalty
525:
207:frameshift mutation
162:Substitution matrix
149:dynamic programming
108:dynamic programming
1279:Comput Appl Biosci
1215:Comput Appl Biosci
1186:Comput Appl Biosci
1132:10.1007/BF02458279
1051:10.1002/prot.10508
939:BMC Bioinformatics
523:
482:
421:
338:
318:
298:
227:
172:
140:
1312:Nucleic Acids Res
560:
559:
341:{\displaystyle k}
321:{\displaystyle k}
170:Blosum-62 Matrix
1366:
1345:
1335:
1302:
1273:
1263:
1238:
1209:
1180:
1151:
1114:
1104:
1071:
1070:
1034:
1019:
1018:
995:Comput Biol Chem
990:
975:
974:
964:
954:
930:
921:
920:
902:
893:
892:
890:
889:
874:
868:
867:
849:
840:
839:
837:
835:
820:
814:
813:
785:
774:
773:
771:
770:
759:
742:
741:
713:
707:
706:
704:
703:
693:"bioinformatics"
688:
682:
681:
679:
678:
672:
661:
653:
642:
641:
635:
627:
625:
624:
609:
603:
602:
600:
599:
584:
526:
491:
489:
488:
483:
430:
428:
427:
422:
347:
345:
344:
339:
327:
325:
324:
319:
307:
305:
304:
299:
95:Global alignment
1374:
1373:
1369:
1368:
1367:
1365:
1364:
1363:
1349:
1348:
1318:(13): 5529–43.
1305:
1276:
1242:Hein J (1989).
1241:
1212:
1183:
1154:
1117:
1082:
1079:
1077:Further reading
1074:
1036:
1035:
1022:
992:
991:
978:
932:
931:
924:
917:
904:
903:
896:
887:
885:
876:
875:
871:
864:
851:
850:
843:
833:
831:
822:
821:
817:
787:
786:
777:
768:
766:
761:
760:
745:
715:
714:
710:
701:
699:
690:
689:
685:
676:
674:
670:
659:
655:
654:
645:
628:
622:
620:
611:
610:
606:
597:
595:
594:. Rosalind Team
586:
585:
578:
574:
565:
514:
512:Time complexity
508:
499:
444:
443:
437:
350:
349:
330:
329:
310:
309:
266:
265:
262:
254:
247:
239:
232:
219:
198:DNA replication
194:
188:
164:
158:
145:local algorithm
132:
126:
124:Local alignment
117:
103:
97:
92:
27:
12:
11:
5:
1372:
1370:
1362:
1361:
1351:
1350:
1347:
1346:
1303:
1274:
1239:
1210:
1181:
1152:
1120:Bull Math Biol
1115:
1078:
1075:
1073:
1072:
1020:
1001:(5): 308–318.
976:
922:
916:978-1420070347
915:
894:
869:
863:978-0203967249
862:
841:
815:
796:(4): 206–214.
775:
743:
708:
683:
643:
604:
575:
573:
570:
564:
561:
558:
557:
556:O(mn lg(m+n))
554:
550:
549:
546:
542:
541:
538:
534:
533:
530:
507:
504:
498:
495:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
436:
433:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
337:
317:
297:
294:
291:
288:
285:
282:
279:
276:
273:
261:
258:
252:
246:
243:
237:
231:
228:
218:
215:
190:Main article:
187:
184:
160:Main article:
157:
156:Scoring matrix
154:
128:Main article:
125:
122:
116:
113:
99:Main article:
96:
93:
91:
88:
87:
86:
80:
73:Spell checking
70:
58:
26:
23:
13:
10:
9:
6:
4:
3:
2:
1371:
1360:
1357:
1356:
1354:
1343:
1339:
1334:
1329:
1325:
1321:
1317:
1313:
1309:
1304:
1300:
1296:
1292:
1288:
1285:(2): 141–50.
1284:
1280:
1275:
1271:
1267:
1262:
1257:
1254:(6): 649–68.
1253:
1249:
1248:Mol Biol Evol
1245:
1240:
1236:
1232:
1228:
1224:
1221:(4): 339–45.
1220:
1216:
1211:
1207:
1203:
1199:
1195:
1192:(3): 285–90.
1191:
1187:
1182:
1178:
1174:
1170:
1166:
1162:
1158:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1121:
1116:
1112:
1108:
1103:
1098:
1094:
1090:
1086:
1081:
1080:
1076:
1068:
1064:
1060:
1056:
1052:
1048:
1044:
1040:
1033:
1031:
1029:
1027:
1025:
1021:
1016:
1012:
1008:
1004:
1000:
996:
989:
987:
985:
983:
981:
977:
972:
968:
963:
958:
953:
948:
944:
940:
936:
929:
927:
923:
918:
912:
908:
901:
899:
895:
883:
879:
873:
870:
865:
859:
855:
848:
846:
842:
829:
825:
819:
816:
811:
807:
803:
799:
795:
791:
784:
782:
780:
776:
764:
758:
756:
754:
752:
750:
748:
744:
739:
735:
731:
727:
723:
719:
712:
709:
698:
694:
687:
684:
673:on 2013-06-26
669:
665:
658:
657:"Gap Penalty"
652:
650:
648:
644:
639:
633:
619:
615:
608:
605:
593:
589:
583:
581:
577:
571:
569:
562:
555:
552:
551:
547:
544:
543:
539:
536:
535:
531:
528:
527:
521:
519:
513:
505:
503:
497:Profile-based
496:
494:
479:
476:
473:
470:
467:
464:
461:
455:
449:
440:
434:
432:
412:
409:
406:
400:
397:
394:
388:
385:
379:
376:
373:
367:
364:
361:
358:
355:
335:
315:
292:
289:
286:
280:
277:
274:
271:
259:
257:
251:
244:
242:
236:
229:
223:
216:
214:
212:
208:
203:
199:
193:
185:
183:
180:
176:
168:
163:
155:
153:
150:
146:
136:
131:
123:
121:
114:
112:
109:
102:
94:
89:
84:
81:
78:
77:edit distance
74:
71:
68:
66:
65:
59:
56:
52:
48:
44:
40:
36:
32:
29:
28:
24:
22:
19:
1315:
1311:
1282:
1278:
1251:
1247:
1218:
1214:
1189:
1185:
1160:
1156:
1123:
1119:
1095:(4): S33-9.
1092:
1088:
1045:(1): 71–87.
1042:
1038:
998:
994:
942:
938:
906:
886:. Retrieved
881:
872:
853:
832:. Retrieved
827:
818:
793:
789:
767:. Retrieved
721:
717:
711:
700:. Retrieved
696:
686:
675:. Retrieved
668:the original
663:
632:cite journal
621:. Retrieved
617:
607:
596:. Retrieved
591:
566:
515:
500:
441:
438:
263:
255:
248:
240:
233:
195:
173:
141:
118:
104:
82:
72:
62:
60:
42:
30:
25:Applications
17:
15:
1163:(1): 1–12.
1126:(1): 1–18.
724:(1): 1–12.
18:Gap penalty
1157:J Mol Biol
888:2014-09-12
769:2012-11-27
702:2014-09-12
677:2014-09-13
623:2014-09-09
598:2021-05-20
588:"Glossary"
572:References
563:Challenges
35:insertions
1148:189884646
477:
410:−
377:−
290:−
281:⋅
39:deletions
1353:Category
1089:Fold Des
1067:20474119
1059:14705025
1039:Proteins
1015:22000802
971:17147805
882:Rosalind
828:Rosalind
810:16545956
592:Rosalind
230:Constant
177:such as
67:function
1342:6462914
1299:2751764
1270:2488477
1235:1498689
1206:8324629
1177:8289235
1140:8819751
1111:9269566
962:1770940
945:: 527.
738:8289235
196:During
47:meiosis
1340:
1333:318937
1330:
1297:
1268:
1233:
1204:
1175:
1146:
1138:
1109:
1065:
1057:
1013:
969:
959:
913:
860:
834:12 Aug
808:
765:. NCBI
736:
548:O(mn)
540:O(mn)
435:Convex
260:Affine
245:Linear
211:cancer
202:Indels
186:Indels
179:BLOSUM
53:, and
43:indels
1144:S2CID
1063:S2CID
671:(PDF)
660:(PDF)
532:Time
529:Type
217:Types
192:Indel
61:Unix
1338:PMID
1295:PMID
1266:PMID
1231:PMID
1202:PMID
1173:PMID
1136:PMID
1107:PMID
1055:PMID
1011:PMID
967:PMID
911:ISBN
858:ISBN
836:2014
806:PMID
734:PMID
638:link
64:diff
1328:PMC
1320:doi
1287:doi
1256:doi
1223:doi
1194:doi
1165:doi
1161:235
1128:doi
1097:doi
1047:doi
1003:doi
957:PMC
947:doi
798:doi
726:doi
722:235
37:or
1355::
1336:.
1326:.
1316:12
1314:.
1310:.
1293:.
1281:.
1264:.
1250:.
1246:.
1229:.
1217:.
1200:.
1188:.
1171:.
1159:.
1142:.
1134:.
1124:58
1122:.
1105:.
1091:.
1087:.
1061:.
1053:.
1043:54
1041:.
1023:^
1009:.
999:35
997:.
979:^
965:.
955:.
941:.
937:.
925:^
897:^
880:.
844:^
826:.
804:.
794:31
792:.
778:^
746:^
732:.
720:.
695:.
662:.
646:^
634:}}
630:{{
616:.
590:.
579:^
474:ln
348::
49:,
16:A
1344:.
1322::
1301:.
1289::
1283:5
1272:.
1258::
1252:6
1237:.
1225::
1219:8
1208:.
1196::
1190:9
1179:.
1167::
1150:.
1130::
1113:.
1099::
1093:2
1069:.
1049::
1017:.
1005::
973:.
949::
943:7
919:.
891:.
866:.
838:.
812:.
800::
772:.
740:.
728::
705:.
680:.
640:)
626:.
601:.
480:L
471:C
468:+
465:A
462:=
459:)
456:L
453:(
450:G
419:)
416:)
413:1
407:L
404:(
401:B
398:+
395:A
392:(
389:k
386:=
383:)
380:1
374:L
371:(
368:B
365:k
362:+
359:A
356:k
336:k
316:k
296:)
293:1
287:L
284:(
278:B
275:+
272:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.