79:
2947:, such as those generated by raindrops, weatherproof covers or dust. By extending the Needleman–Wunsch algorithm, a line in the 'left' image can be associated to a curve in the 'right' image by finding the alignment with the highest score in a three-dimensional array (or matrix). Experiments demonstrated that such extension allows dense pixel matching between unrectified or distorted images.
3379:
25:
1336:
Different scoring matrices have been statistically constructed which give weight to different actions appropriate to a particular scenario. Having weighted scoring matrices is particularly important in protein sequence alignment due to the varying frequency of the different amino acids. There are two
1357:
When aligning sequences there are often gaps (i.e. indels), sometimes large ones. Biologically, a large gap is more likely to occur as one large deletion as opposed to multiple single deletions. Hence two small indels should have a worse score than one large one. The simple and common way to do this
1149:
More complicated scoring systems attribute values not only for the type of alteration, but also for the letters that are involved. For example, a match between A and A may be given 1, but a match between T and T may be given 4. Here (assuming the first scoring system) more importance is given to the
1244:
Each score represents a switch from one of the letters the cell matches to the other. Hence this represents all possible matches and mismatches (for an alphabet of ACGT). Note all the matches go along the diagonal, also not all the table needs to be filled, only this triangle because the scores are
537:
Given there is no 'top' or 'top-left' cells for the first row only the existing cell to the left can be used to calculate the score of each cell. Hence −1 is added for each shift to the right as this represents an indel from the previous score. This results in the first row being 0, −1, −2, −3, −4,
521:
Start with a zero in the first row, first column (not including the cells containing nucleotides). Move through the cells row by row, calculating the score for each cell. The score is calculated by comparing the scores of the cells neighboring to the left, top or top-left (diagonal) of the cell and
213:
to compare biological sequences. The algorithm was developed by Saul B. Needleman and
Christian D. Wunsch and published in 1970. The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an
2903:
Recent development has focused on improving the time and space cost of the algorithm while maintaining quality. For example, in 2013, a Fast
Optimal Global Sequence Alignment Algorithm (FOGSAA), suggested alignment of nucleotide/protein sequences faster than other optimal global alignment methods,
222:
technique. The
Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible
1126:
For this system the alignment score will represent the edit distance between the two strings. Different scoring systems can be devised for different situations, for example if gaps are considered very bad for your alignment you may use a scoring system that penalises gaps heavily, such as:
250:
First construct a grid such as one shown in Figure 1 above. Start the first string in the top of the third column and start the other string at the start of the third row. Fill out the rest of the column and row headers as in Figure 1. There should be no numbers in the grid yet.
2229:
gives the maximum score among all possible alignments. To compute an alignment that actually gives this score, you start from the bottom right cell, and compare the value with the three possible sources (Match, Insert, and Delete above) to see which it came from. If Match, then
2904:
including the
Needleman–Wunsch algorithm. The paper claims that when compared to the Needleman–Wunsch algorithm, FOGSAA achieves a time gain of 70–90% for highly similar nucleotide sequences (with > 80% similarity), and 54–70% for sequences having 30–80% similarity.
1078:
If there are multiple arrows to choose from, they represent a branching of the alignments. If two or more branches all belong to paths from the bottom right to the top left cell, they are equally viable alignments. In this case, note the paths as separate alignment
2900:, particularly when the quality of the global alignment is of the utmost importance. However, the algorithm is expensive with respect to time and space, proportional to the product of the length of two sequences and hence is not suitable for long sequences.
2857:
529:
The diagonal path represents a match/mismatch, so take the score of the top-left diagonal cell and add the score for match if the corresponding bases (letters) in the row and column are matching or the score for mismatch if they do
2128:
2923:
Stereo matching is an essential step in the process of 3D reconstruction from a pair of stereo images. When images have been rectified, an analogy can be drawn between aligning nucleotide and protein sequences and matching
1358:
is via a large gap-start score for a new indel and a smaller gap-extension score for every letter which extends the indel. For example, new-indel may cost -5 and extend-indel may cost -1. In this way an alignment such as:
846:
The cell which gave the highest candidate score must also be recorded. In the completed diagram in figure 1 above, this is represented as an arrow from the cell in row and column 2 to the cell in row and column 1.
488:
Each of these scenarios is assigned a score and the sum of the scores of all the pairings is the score of the whole alignment candidate. Different systems exist for assigning scores; some have been outlined in the
1074:
A horizontal or vertical arrow represents an indel. Vertical arrows will align a gap ("-") to the letter of the row (the "side" sequence), horizontal arrows will align a gap to the letter of the column (the "top"
1107:
The simplest scoring schemes simply give a value for each match, mismatch and indel. The step-by-step guide above uses match = 1, mismatch = −1, indel = −1. Thus the lower the alignment score the larger the
2866:
A penalty factor, a number subtracted for every gap made, may be assessed as a barrier to allowing the gap. The penalty factor could be a function of the size and/or direction of the gap.
3401:
1059:
Filling in the table in this manner gives the scores of all possible alignment candidates, the score in the cell on the bottom right represents the alignment score for the best alignment.
1153:
In order to represent all the possible combinations of letters and their resulting scores a similarity matrix is used. The similarity matrix for the most basic system is represented as:
1067:
Mark a path from the cell on the bottom right back to the cell on the top left by following the direction of the arrows. From this path, the sequence is constructed by these rules:
1056:
In this case, all directions reaching the highest candidate score must be noted as possible origin cells in the finished diagram in figure 1, e.g. in the cell in row and column 6.
1705:
1850:
1808:
2591:
1951:
1908:
2621:
2678:
2668:
Needleman and Wunsch describe their algorithm explicitly for the case when the alignment is penalized solely by the matches and mismatches, and gaps have no penalty (
2656:
2444:
2227:
1770:
1609:
2862:
The corresponding dynamic programming algorithm takes cubic time. The paper also points out that the recursion can accommodate arbitrary gap penalization formulas:
2545:
2336:
2309:
2282:
2255:
1737:
1657:
179:
136:
2473:
2513:
2493:
3006:
Needleman, Saul B. & Wunsch, Christian D. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins".
1150:
Ts matching than the As, i.e. the Ts matching is assumed to be more significant to the alignment. This weighting based on letters also applies to mismatches.
526:
The path from the top or left cell represents an indel pairing, so take the scores of the left and the top cell, and add the score for indel to each of them.
754:
The first case with existing scores in all 3 directions is the intersection of our first letters (in this case G and G). The surrounding cells are below:
1964:
43:
3461:
2939:
or calibration, it is sometimes impossible or impractical since the computational cost of accurate rectification models prohibit their usage in
2665:
The original purpose of the algorithm described by
Needleman and Wunsch was to find similarities in the amino acid sequences of two proteins.
3041:
3727:
1245:
reciprocal.= (Score for A → C = Score for C → A). If implementing the T-T = 4 rule from above the following similarity matrix is produced:
522:
adding the appropriate score for match, mismatch or indel. Take the maximum of the candidate scores for each of the three possibilities:
538:−5, −6, −7. The same applies to the first column as only the existing score above each cell can be used. Thus the resulting table is:
3622:
1071:
A diagonal arrow represents a match or mismatch, so the letter of the column and the letter of the row of the origin cell will align.
3661:
3587:
2870:
A better dynamic programming algorithm with quadratic running time for the same problem (no gap penalty) was introduced later by
3844:
3592:
458:
Next, decide how to score each individual pair of letters. Using the example above, one possible alignment candidate might be:
2338:
is aligned with a gap. (In general, more than one choice may have the same value, leading to alternative optimal alignments.)
3849:
3597:
2874:
in 1972. Similar quadratic-time algorithms were discovered independently by T. K. Vintsyuk in 1968 for speech processing (
1857:
3442:
NW-align: A protein sequence-to-sequence alignment program by
Needleman-Wunsch algorithm (online server and source code)
2885:
Needleman and Wunsch formulated their problem in terms of maximizing similarity. Another possibility is to minimize the
3839:
3808:
3582:
800:
The top neighbor has score −1 and moving from there represents an indel, so add the score for indel: (−1) + (−1) = (−2)
3676:
3617:
3489:
3427:
3076:
61:
3524:
2897:
219:
797:
The diagonal top-left neighbor has score 0. The pairing of G and G is a match, so add the score for match: 0+1 = 1
3456:
3397:
484:
Indel (Insertion or
Deletion): The best alignment involves one letter aligning to a gap in the other string.
39:
3854:
3709:
3564:
2961:
2956:
142:
99:
1666:
3788:
3514:
3793:
3671:
3638:
3574:
3803:
3699:
3643:
3544:
3498:
1660:
232:
3798:
3602:
3534:
3409:
3405:
3389:
1817:
1775:
2932:, since both tasks aim at establishing optimal correspondence between two strings of characters.
2550:
3747:
2852:{\displaystyle F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}}
2594:
1341:
2943:
applications. Moreover, none of these models is suitable when a camera lens displays unexpected
1914:
1871:
2918:
2600:
78:
3752:
3694:
3554:
3482:
2626:
2419:
2202:
1745:
1584:
1364:
which has multiple equal alignments, some with multiple small alignments will now align as:
3559:
3310:
3146:
2976:
2971:
2890:
2886:
2875:
2518:
2314:
2287:
2260:
2233:
1710:
1630:
1566:
1562:
1109:
152:
109:
2449:
1337:
broad families of scoring matrices, each with further alterations for specific scenarios:
8:
3757:
2940:
2936:
210:
3314:
3150:
3686:
3653:
3357:
Dense pixel matching between unrectified and distorted images using dynamic programming
3331:
3298:
3252:
3233:
3209:
2981:
2879:
2498:
2478:
1083:
Following these rules, the steps for one possible alignment candidate in figure 1 are:
199:
92:
3169:
3134:
3818:
3355:
3336:
3213:
3174:
3118:
3101:
3082:
3072:
3023:
3019:
2133:
The pseudo-code for the algorithm to compute the F matrix therefore looks like this:
1379:
3256:
3813:
3783:
3737:
3539:
3475:
3353:
3326:
3318:
3279:
3242:
3201:
3164:
3154:
3113:
3015:
2123:{\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}
1112:, for this scoring system one wants a high score. Another scoring system might be:
215:
145:
470:
The letters may match, mismatch, or be matched to a gap (a deletion or insertion (
3666:
3607:
3519:
2966:
2475:
operation. Thus the time complexity of the algorithm for two sequences of length
2188:) Delete ← F(i−1, j) + d Insert ← F(i, j−1) + d F(i,j) ←
102:
3452:
An interactive
Javascript-based visual explanation of Needleman-Wunsch Algorithm
803:
The left neighbor also has score −1, represents an indel and also produces (−2).
214:
optimal solution to the larger problem. It is also sometimes referred to as the
3719:
3612:
2400:+ AlignmentA AlignmentB ← "−" + AlignmentB i ← i − 1 }
850:
In the next example, the diagonal step for both X and Y represents a mismatch:
534:
The resulting score for the cell is the highest of the three candidate scores.
195:
3441:
3270:
Sellers PH (1974). "On the theory and computation of evolutionary distances".
493:
section below. For now, the system used by
Needleman and Wunsch will be used:
3833:
3529:
3506:
3086:
2871:
236:
3360:. International Conference on Computer Vision Theory and Applications. Rome.
2935:
Although in many applications image rectification can be performed, e.g. by
1004:
The highest candidate score may be reached by two of the neighboring cells:
3732:
3549:
3340:
1370:
or any alignment with a 4 long gap in preference over multiple small gaps.
3451:
3247:
3228:
3178:
3027:
3742:
2944:
1406:
3159:
2893:. Peter H. Sellers showed in 1974 that the two problems are equivalent.
1772:
will be assigned to be the optimal score for the alignment of the first
1707:
space, but is otherwise similar to
Needleman-Wunsch (and still requires
3205:
2929:
2547:. It has been shown that it is possible to improve the running time to
206:
3322:
3005:
1094:↓ (branch) → TGCG → -TGCG → ... → TACA → TTACA → ...
2673:
191:
3283:
3192:
Vintsyuk TK (1968). "Speech discrimination by dynamic programming".
3408:
external links, and converting useful links where appropriate into
3354:
Thevenon, J; Martinez-del-Rincon, J; Dieny, R; Nebel, J-C (2012).
3778:
3297:
Chakraborty, Angana; Bandyopadhyay, Sanghamitra (29 April 2013).
202:
2896:
The Needleman–Wunsch algorithm is still widely used for optimal
1561:
To find the alignment with the highest score, a two-dimensional
2925:
1346:
3464:
R package implementing Needleman–Wunsch algorithm among others
2404:{ AlignmentA ← "−" + AlignmentA AlignmentB ← B
504:
For the Example above, the score of the alignment would be 0:
2660:
481:
Mismatch: The two letters at the current index are different.
471:
3071:. Boca Raton: Chapman & Hall/CRC Press. pp. 34–35.
3069:
Algorithms in bioinformatics : a practical introduction
3762:
2385:+ AlignmentB i ← i − 1 j ← j − 1 }
3467:
3299:"FOGSAA: Fast Optimal Global Sequence Alignment Algorithm"
3139:
Proceedings of the National Academy of Sciences of the USA
1513:
with a gap penalty of −5, would have the following score:
3446:
3135:"Matching sequences under deletion/insertion constraints"
807:
The highest candidate is 1 and is entered into the cell:
478:
Match: The two letters at the current index are the same.
3296:
2907:
2396:
F(i, j) == F(i−1, j) + d) { AlignmentA ← A
83:
Figure 1: Needleman-Wunsch pairwise sequence alignment
2681:
2672:=0). The original publication from 1970 suggests the
2629:
2603:
2553:
2521:
2501:
2481:
2452:
2422:
2317:
2290:
2263:
2236:
2205:
1967:
1917:
1874:
1820:
1778:
1748:
1713:
1669:
1633:
1587:
1557:= −3 + 7 + 10 − (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1
1373:
155:
112:
3102:"A faster algorithm computing string edit distances"
1663:
only holds a subset of the array in memory and uses
3100:Masek, William; Paterson, Michael (February 1980).
209:sequences. It was one of the first applications of
34:
may be too technical for most readers to understand
2851:
2650:
2615:
2585:
2539:
2507:
2487:
2467:
2438:
2330:
2303:
2276:
2249:
2221:
2122:
1945:
1902:
1844:
1802:
1764:
1731:
1699:
1651:
1611:. There is one row for each character in sequence
1603:
173:
130:
3392:may not follow Knowledge's policies or guidelines
1378:Scores for aligned characters are specified by a
1090:A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA →
1086:G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG →
3831:
3457:Sequence Alignment Techniques at Technology Blog
3447:A live Javascript-based demo of Needleman–Wunsch
2699:
1984:
1957:Recursion, based on the principle of optimality:
1676:
1615:, and one column for each character in sequence
1062:
3483:
3226:
3099:
941:For both X and Y, the highest score is zero:
793:This cell has three possible candidate sums:
3220:
2846:
2726:
1691:
1679:
453:
3191:
3001:
2999:
2997:
2311:is aligned with a gap, and if Insert, then
2180:(B) { Match ← F(i−1, j−1) + S(A
3490:
3476:
3269:
2661:Historical notes and algorithm development
2088:
2056:
1416:For example, if the similarity matrix was
77:
3428:Learn how and when to remove this message
3330:
3246:
3229:"The string-to-string correction problem"
3168:
3158:
3132:
3117:
3066:
2912:
62:Learn how and when to remove this message
46:, without removing the technical details.
3662:Comparison of regular-expression engines
2994:
1102:
245:
16:Method for aligning biological sequences
3185:
3106:Journal of Computer and System Sciences
2408:+ AlignmentB j ← j − 1 } }
1619:. Thus, if aligning sequences of sizes
516:
231:This algorithm can be used for any two
3832:
3263:
3126:
3623:Zhu–Takaoka string matching algorithm
3471:
223:alignments having the highest score.
44:make it understandable to non-experts
3372:
3062:
3060:
3058:
2341:AlignmentA ← "" AlignmentB ← "" i ←
1700:{\displaystyle \Theta (\min\{n,m\})}
1144:
490:
18:
3588:Boyer–Moore string-search algorithm
3272:SIAM Journal on Applied Mathematics
2908:Applications outside bioinformatics
2381:+ AlignmentA AlignmentB ← B
13:
1670:
1627:, the amount of memory used is in
1374:Advanced presentation of algorithm
1097:
239:as examples as shown in Figure 1:
14:
3866:
3677:Nondeterministic finite automaton
3618:Two-way string-matching algorithm
3368:
3055:
2889:between sequences, introduced by
2446:for each cell in the table is an
1742:As the algorithm progresses, the
3377:
1397:is the similarity of characters
513:+−++−−+− −> 1*4 + (−1)*4 = 0
235:. This guide will use two small
23:
3347:
2878:), and by Robert A. Wagner and
2597:. Since the algorithm fills an
2377:)) { AlignmentA ← A
1573:is allocated. The entry in row
226:
3593:Boyer–Moore–Horspool algorithm
3583:Apostolico–Giancarlo algorithm
3290:
3227:Wagner RA, Fischer MJ (1974).
3093:
3034:
2843:
2817:
2783:
2757:
2642:
2633:
2623:table the space complexity is
2580:
2557:
2534:
2525:
2462:
2456:
2199:matrix is computed, the entry
2192:(Match, Insert, Delete) }
2117:
2050:
2024:
1987:
1726:
1717:
1694:
1673:
1646:
1637:
1352:
168:
159:
125:
116:
1:
3845:Sequence alignment algorithms
2987:
2882:in 1974 for string matching.
2411:
2284:are aligned, if Delete, then
1845:{\displaystyle j=0,\dotsc ,m}
1803:{\displaystyle i=0,\dotsc ,n}
1063:Tracing arrows back to origin
3598:Knuth–Morris–Pratt algorithm
3525:Damerau–Levenshtein distance
3119:10.1016/0022-0000(80)90002-1
3020:10.1016/0022-2836(70)90057-4
3008:Journal of Molecular Biology
2586:{\displaystyle O(mn/\log n)}
2369:F(i, j) == F(i−1, j−1) + S(A
1860:is then applied as follows:
7:
3850:Computational phylogenetics
3789:Compressed pattern matching
3515:Approximate string matching
3497:
2950:
10:
3871:
3794:Longest common subsequence
3705:Needleman–Wunsch algorithm
3575:String-searching algorithm
2916:
1946:{\displaystyle F_{i0}=d*i}
1903:{\displaystyle F_{0j}=d*j}
937:Top-Left: (−1)+(−1) = (−2)
923:Top-Left: (−1)+(−1) = (−2)
188:Needleman–Wunsch algorithm
3840:Bioinformatics algorithms
3804:Sequential pattern mining
3771:
3718:
3685:
3652:
3644:Commentz-Walter algorithm
3632:Multiple string searching
3631:
3573:
3565:Wagner–Fischer algorithm
3505:
2616:{\displaystyle n\times m}
1488:
1471:
1454:
1437:
1432:
1429:
1426:
1423:
1421:
1317:
1300:
1283:
1266:
1261:
1258:
1255:
1252:
1250:
1225:
1208:
1191:
1174:
1169:
1166:
1163:
1160:
1158:
1030:
1019:
987:
971:
958:
896:
880:
867:
831:
821:
778:
768:
730:
708:
686:
664:
642:
620:
598:
570:
454:Choosing a scoring system
430:
409:
388:
367:
346:
325:
304:
283:
141:
98:
88:
76:
3814:String rewriting systems
3799:Longest common substring
3710:Smith–Waterman algorithm
3535:Gestalt pattern matching
3067:Wing-Kin., Sung (2010).
2962:Smith–Waterman algorithm
2957:Wagner–Fischer algorithm
1510:AGACTAGTTAC CGA---GACGT
1049:Top-Left: (1)+(−1) = (0)
3748:Generalized suffix tree
3672:Thompson's construction
2595:Method of Four Russians
2158:(B) F(0,j) ← d * j
2147:(A) F(i,0) ← d * i
1858:principle of optimality
3700:Hirschberg's algorithm
2919:Computer stereo vision
2913:Computer stereo vision
2868:
2853:
2652:
2651:{\displaystyle O(mn).}
2617:
2587:
2541:
2509:
2489:
2469:
2440:
2439:{\displaystyle F_{ij}}
2332:
2305:
2278:
2251:
2223:
2222:{\displaystyle F_{nm}}
2136:d ← Gap penalty score
2124:
1947:
1904:
1846:
1804:
1766:
1765:{\displaystyle F_{ij}}
1733:
1701:
1661:Hirschberg's algorithm
1653:
1605:
1604:{\displaystyle F_{ij}}
934:Left: (−2)+(−1) = (−3)
175:
132:
3555:Levenshtein automaton
3545:Jaro–Winkler distance
3248:10.1145/321796.321811
2864:
2854:
2653:
2618:
2588:
2542:
2540:{\displaystyle O(mn)}
2510:
2490:
2470:
2441:
2333:
2331:{\displaystyle B_{j}}
2306:
2304:{\displaystyle A_{i}}
2279:
2277:{\displaystyle B_{j}}
2252:
2250:{\displaystyle A_{i}}
2224:
2125:
1948:
1905:
1847:
1805:
1767:
1734:
1732:{\displaystyle O(nm)}
1702:
1654:
1652:{\displaystyle O(nm)}
1606:
1103:Basic scoring schemes
1052:Left: (0)+(−1) = (−1)
920:Left: (+1)+(−1) = (0)
917:Top: (−2)+(−1) = (−3)
500:Mismatch or Indel: −1
246:Constructing the grid
176:
174:{\displaystyle O(mn)}
133:
131:{\displaystyle O(mn)}
3603:Rabin–Karp algorithm
3560:Levenshtein distance
3398:improve this article
2977:Dynamic time warping
2972:Levenshtein distance
2891:Vladimir Levenshtein
2679:
2627:
2601:
2551:
2519:
2499:
2479:
2468:{\displaystyle O(1)}
2450:
2420:
2416:Computing the score
2315:
2288:
2261:
2234:
2203:
1965:
1915:
1872:
1818:
1776:
1746:
1711:
1667:
1631:
1585:
1507:then the alignment:
517:Filling in the table
153:
110:
3855:Dynamic programming
3758:Ternary search tree
3410:footnote references
3315:2013NatSR...3E1746C
3160:10.1073/pnas.69.1.4
3151:1972PNAS...69....4S
2937:camera resectioning
1581:is denoted here by
1405:. It uses a linear
1046:Top: (1)+(−1) = (0)
931:Top: (1)+(−1) = (0)
211:dynamic programming
3687:Sequence alignment
3654:Regular expression
3303:Scientific Reports
3234:Journal of the ACM
3206:10.1007/BF01074755
3133:Sankoff D (1972).
2982:Sequence alignment
2880:Michael J. Fischer
2849:
2725:
2648:
2613:
2583:
2537:
2505:
2485:
2465:
2436:
2328:
2301:
2274:
2247:
2219:
2120:
1943:
1900:
1842:
1800:
1762:
1729:
1697:
1649:
1601:
1367:GAAAAAAT GAA----T
1361:GAAAAAAT G--A-A-T
218:algorithm and the
171:
128:
93:Sequence alignment
3827:
3826:
3819:String operations
3438:
3437:
3430:
3323:10.1038/srep01746
2698:
2508:{\displaystyle m}
2488:{\displaystyle n}
1505:
1504:
1380:similarity matrix
1334:
1333:
1242:
1241:
1145:Similarity matrix
1043:
1042:
1002:
1001:
911:
910:
844:
843:
791:
790:
752:
751:
451:
450:
184:
183:
72:
71:
64:
3862:
3784:Pattern matching
3738:Suffix automaton
3540:Hamming distance
3492:
3485:
3478:
3469:
3468:
3433:
3426:
3422:
3419:
3413:
3381:
3380:
3373:
3362:
3361:
3351:
3345:
3344:
3334:
3294:
3288:
3287:
3267:
3261:
3260:
3250:
3224:
3218:
3217:
3189:
3183:
3182:
3172:
3162:
3130:
3124:
3123:
3121:
3097:
3091:
3090:
3064:
3053:
3052:
3050:
3048:
3042:"bioinformatics"
3038:
3032:
3031:
3003:
2898:global alignment
2858:
2856:
2855:
2850:
2842:
2841:
2829:
2828:
2810:
2809:
2782:
2781:
2769:
2768:
2750:
2749:
2724:
2694:
2693:
2657:
2655:
2654:
2649:
2622:
2620:
2619:
2614:
2592:
2590:
2589:
2584:
2570:
2546:
2544:
2543:
2538:
2514:
2512:
2511:
2506:
2494:
2492:
2491:
2486:
2474:
2472:
2471:
2466:
2445:
2443:
2442:
2437:
2435:
2434:
2357:j > 0) {
2337:
2335:
2334:
2329:
2327:
2326:
2310:
2308:
2307:
2302:
2300:
2299:
2283:
2281:
2280:
2275:
2273:
2272:
2256:
2254:
2253:
2248:
2246:
2245:
2228:
2226:
2225:
2220:
2218:
2217:
2129:
2127:
2126:
2121:
2110:
2109:
2078:
2077:
2049:
2048:
2036:
2035:
2017:
2016:
1980:
1979:
1952:
1950:
1949:
1944:
1930:
1929:
1909:
1907:
1906:
1901:
1887:
1886:
1851:
1849:
1848:
1843:
1809:
1807:
1806:
1801:
1771:
1769:
1768:
1763:
1761:
1760:
1738:
1736:
1735:
1730:
1706:
1704:
1703:
1698:
1658:
1656:
1655:
1650:
1610:
1608:
1607:
1602:
1600:
1599:
1554:
1419:
1418:
1412:
1396:
1248:
1247:
1156:
1155:
1007:
1006:
944:
943:
853:
852:
810:
809:
757:
756:
541:
540:
512:
509:
467:
464:
254:
253:
242:GCATGCG GATTACA
220:global alignment
216:optimal matching
180:
178:
177:
172:
146:space complexity
137:
135:
134:
129:
81:
74:
73:
67:
60:
56:
53:
47:
27:
26:
19:
3870:
3869:
3865:
3864:
3863:
3861:
3860:
3859:
3830:
3829:
3828:
3823:
3767:
3714:
3681:
3667:Regular grammar
3648:
3627:
3608:Raita algorithm
3569:
3520:Bitap algorithm
3501:
3496:
3434:
3423:
3417:
3414:
3395:
3386:This article's
3382:
3378:
3371:
3366:
3365:
3352:
3348:
3295:
3291:
3284:10.1137/0126070
3268:
3264:
3225:
3221:
3190:
3186:
3131:
3127:
3098:
3094:
3079:
3065:
3056:
3046:
3044:
3040:
3039:
3035:
3004:
2995:
2990:
2967:Sequence mining
2953:
2921:
2915:
2910:
2837:
2833:
2824:
2820:
2793:
2789:
2777:
2773:
2764:
2760:
2733:
2729:
2702:
2686:
2682:
2680:
2677:
2676:
2663:
2628:
2625:
2624:
2602:
2599:
2598:
2566:
2552:
2549:
2548:
2520:
2517:
2516:
2500:
2497:
2496:
2480:
2477:
2476:
2451:
2448:
2447:
2427:
2423:
2421:
2418:
2417:
2414:
2409:
2407:
2399:
2384:
2380:
2376:
2372:
2322:
2318:
2316:
2313:
2312:
2295:
2291:
2289:
2286:
2285:
2268:
2264:
2262:
2259:
2258:
2241:
2237:
2235:
2232:
2231:
2210:
2206:
2204:
2201:
2200:
2193:
2187:
2183:
2093:
2089:
2061:
2057:
2044:
2040:
2031:
2027:
1994:
1990:
1972:
1968:
1966:
1963:
1962:
1922:
1918:
1916:
1913:
1912:
1879:
1875:
1873:
1870:
1869:
1819:
1816:
1815:
1777:
1774:
1773:
1753:
1749:
1747:
1744:
1743:
1712:
1709:
1708:
1668:
1665:
1664:
1632:
1629:
1628:
1592:
1588:
1586:
1583:
1582:
1517:
1511:
1410:
1383:
1376:
1368:
1362:
1355:
1147:
1141:
1105:
1100:
1098:Scoring systems
1095:
1065:
519:
514:
510:
507:
491:Scoring systems
468:
465:
462:
456:
248:
243:
229:
154:
151:
150:
111:
108:
107:
84:
68:
57:
51:
48:
40:help improve it
37:
28:
24:
17:
12:
11:
5:
3868:
3858:
3857:
3852:
3847:
3842:
3825:
3824:
3822:
3821:
3816:
3811:
3806:
3801:
3796:
3791:
3786:
3781:
3775:
3773:
3769:
3768:
3766:
3765:
3760:
3755:
3750:
3745:
3740:
3735:
3730:
3724:
3722:
3720:Data structure
3716:
3715:
3713:
3712:
3707:
3702:
3697:
3691:
3689:
3683:
3682:
3680:
3679:
3674:
3669:
3664:
3658:
3656:
3650:
3649:
3647:
3646:
3641:
3635:
3633:
3629:
3628:
3626:
3625:
3620:
3615:
3613:Trigram search
3610:
3605:
3600:
3595:
3590:
3585:
3579:
3577:
3571:
3570:
3568:
3567:
3562:
3557:
3552:
3547:
3542:
3537:
3532:
3527:
3522:
3517:
3511:
3509:
3503:
3502:
3495:
3494:
3487:
3480:
3472:
3466:
3465:
3459:
3454:
3449:
3444:
3436:
3435:
3390:external links
3385:
3383:
3376:
3370:
3369:External links
3367:
3364:
3363:
3346:
3289:
3278:(4): 787–793.
3262:
3241:(1): 168–173.
3219:
3184:
3125:
3092:
3077:
3054:
3033:
2992:
2991:
2989:
2986:
2985:
2984:
2979:
2974:
2969:
2964:
2959:
2952:
2949:
2917:Main article:
2914:
2911:
2909:
2906:
2876:"time warping"
2848:
2845:
2840:
2836:
2832:
2827:
2823:
2819:
2816:
2813:
2808:
2805:
2802:
2799:
2796:
2792:
2788:
2785:
2780:
2776:
2772:
2767:
2763:
2759:
2756:
2753:
2748:
2745:
2742:
2739:
2736:
2732:
2728:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2701:
2697:
2692:
2689:
2685:
2662:
2659:
2647:
2644:
2641:
2638:
2635:
2632:
2612:
2609:
2606:
2582:
2579:
2576:
2573:
2569:
2565:
2562:
2559:
2556:
2536:
2533:
2530:
2527:
2524:
2504:
2484:
2464:
2461:
2458:
2455:
2433:
2430:
2426:
2413:
2410:
2405:
2397:
2382:
2378:
2374:
2370:
2340:
2325:
2321:
2298:
2294:
2271:
2267:
2244:
2240:
2216:
2213:
2209:
2185:
2181:
2135:
2131:
2130:
2119:
2116:
2113:
2108:
2105:
2102:
2099:
2096:
2092:
2087:
2084:
2081:
2076:
2073:
2070:
2067:
2064:
2060:
2055:
2052:
2047:
2043:
2039:
2034:
2030:
2026:
2023:
2020:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1993:
1989:
1986:
1983:
1978:
1975:
1971:
1959:
1958:
1954:
1953:
1942:
1939:
1936:
1933:
1928:
1925:
1921:
1910:
1899:
1896:
1893:
1890:
1885:
1882:
1878:
1866:
1865:
1852:characters in
1841:
1838:
1835:
1832:
1829:
1826:
1823:
1814:and the first
1810:characters in
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1759:
1756:
1752:
1728:
1725:
1722:
1719:
1716:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1648:
1645:
1642:
1639:
1636:
1598:
1595:
1591:
1559:
1558:
1555:
1509:
1503:
1502:
1499:
1496:
1493:
1490:
1486:
1485:
1482:
1479:
1476:
1473:
1469:
1468:
1465:
1462:
1459:
1456:
1452:
1451:
1448:
1445:
1442:
1439:
1435:
1434:
1431:
1428:
1425:
1422:
1409:, here called
1375:
1372:
1366:
1360:
1354:
1351:
1350:
1349:
1344:
1332:
1331:
1328:
1325:
1322:
1319:
1315:
1314:
1311:
1308:
1305:
1302:
1298:
1297:
1294:
1291:
1288:
1285:
1281:
1280:
1277:
1274:
1271:
1268:
1264:
1263:
1260:
1257:
1254:
1251:
1240:
1239:
1236:
1233:
1230:
1227:
1223:
1222:
1219:
1216:
1213:
1210:
1206:
1205:
1202:
1199:
1196:
1193:
1189:
1188:
1185:
1182:
1179:
1176:
1172:
1171:
1168:
1165:
1162:
1159:
1146:
1143:
1139:
1138:
1135:
1132:
1124:
1123:
1120:
1117:
1104:
1101:
1099:
1096:
1085:
1081:
1080:
1076:
1072:
1064:
1061:
1054:
1053:
1050:
1047:
1041:
1040:
1035:
1032:
1028:
1027:
1024:
1021:
1017:
1016:
1013:
1010:
1000:
999:
997:
992:
989:
985:
984:
979:
976:
973:
969:
968:
965:
962:
959:
956:
955:
952:
949:
947:
939:
938:
935:
932:
925:
924:
921:
918:
909:
908:
906:
901:
898:
894:
893:
888:
885:
882:
878:
877:
874:
871:
868:
865:
864:
861:
858:
856:
842:
841:
836:
833:
829:
828:
825:
822:
819:
818:
815:
813:
805:
804:
801:
798:
789:
788:
783:
780:
776:
775:
772:
769:
766:
765:
762:
760:
750:
749:
747:
745:
743:
741:
739:
737:
735:
732:
728:
727:
725:
723:
721:
719:
717:
715:
713:
710:
706:
705:
703:
701:
699:
697:
695:
693:
691:
688:
684:
683:
681:
679:
677:
675:
673:
671:
669:
666:
662:
661:
659:
657:
655:
653:
651:
649:
647:
644:
640:
639:
637:
635:
633:
631:
629:
627:
625:
622:
618:
617:
615:
613:
611:
609:
607:
605:
603:
600:
596:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
567:
564:
561:
558:
555:
552:
549:
546:
544:
532:
531:
527:
518:
515:
506:
502:
501:
498:
486:
485:
482:
479:
460:
455:
452:
449:
448:
446:
444:
442:
440:
438:
436:
434:
432:
428:
427:
425:
423:
421:
419:
417:
415:
413:
411:
407:
406:
404:
402:
400:
398:
396:
394:
392:
390:
386:
385:
383:
381:
379:
377:
375:
373:
371:
369:
365:
364:
362:
360:
358:
356:
354:
352:
350:
348:
344:
343:
341:
339:
337:
335:
333:
331:
329:
327:
323:
322:
320:
318:
316:
314:
312:
310:
308:
306:
302:
301:
299:
297:
295:
293:
291:
289:
287:
284:
281:
280:
277:
274:
271:
268:
265:
262:
259:
257:
247:
244:
241:
228:
225:
196:bioinformatics
182:
181:
170:
167:
164:
161:
158:
148:
139:
138:
127:
124:
121:
118:
115:
105:
96:
95:
90:
86:
85:
82:
70:
69:
52:September 2013
31:
29:
22:
15:
9:
6:
4:
3:
2:
3867:
3856:
3853:
3851:
3848:
3846:
3843:
3841:
3838:
3837:
3835:
3820:
3817:
3815:
3812:
3810:
3807:
3805:
3802:
3800:
3797:
3795:
3792:
3790:
3787:
3785:
3782:
3780:
3777:
3776:
3774:
3770:
3764:
3761:
3759:
3756:
3754:
3751:
3749:
3746:
3744:
3741:
3739:
3736:
3734:
3731:
3729:
3726:
3725:
3723:
3721:
3717:
3711:
3708:
3706:
3703:
3701:
3698:
3696:
3693:
3692:
3690:
3688:
3684:
3678:
3675:
3673:
3670:
3668:
3665:
3663:
3660:
3659:
3657:
3655:
3651:
3645:
3642:
3640:
3637:
3636:
3634:
3630:
3624:
3621:
3619:
3616:
3614:
3611:
3609:
3606:
3604:
3601:
3599:
3596:
3594:
3591:
3589:
3586:
3584:
3581:
3580:
3578:
3576:
3572:
3566:
3563:
3561:
3558:
3556:
3553:
3551:
3548:
3546:
3543:
3541:
3538:
3536:
3533:
3531:
3530:Edit distance
3528:
3526:
3523:
3521:
3518:
3516:
3513:
3512:
3510:
3508:
3507:String metric
3504:
3500:
3493:
3488:
3486:
3481:
3479:
3474:
3473:
3470:
3463:
3460:
3458:
3455:
3453:
3450:
3448:
3445:
3443:
3440:
3439:
3432:
3429:
3421:
3411:
3407:
3406:inappropriate
3403:
3399:
3393:
3391:
3384:
3375:
3374:
3359:
3358:
3350:
3342:
3338:
3333:
3328:
3324:
3320:
3316:
3312:
3308:
3304:
3300:
3293:
3285:
3281:
3277:
3273:
3266:
3258:
3254:
3249:
3244:
3240:
3236:
3235:
3230:
3223:
3215:
3211:
3207:
3203:
3199:
3195:
3188:
3180:
3176:
3171:
3166:
3161:
3156:
3152:
3148:
3144:
3140:
3136:
3129:
3120:
3115:
3111:
3107:
3103:
3096:
3088:
3084:
3080:
3078:9781420070330
3074:
3070:
3063:
3061:
3059:
3043:
3037:
3029:
3025:
3021:
3017:
3014:(3): 443–53.
3013:
3009:
3002:
3000:
2998:
2993:
2983:
2980:
2978:
2975:
2973:
2970:
2968:
2965:
2963:
2960:
2958:
2955:
2954:
2948:
2946:
2942:
2938:
2933:
2931:
2928:belonging to
2927:
2920:
2905:
2901:
2899:
2894:
2892:
2888:
2887:edit distance
2883:
2881:
2877:
2873:
2872:David Sankoff
2867:
2863:
2860:
2838:
2834:
2830:
2825:
2821:
2814:
2811:
2806:
2803:
2800:
2797:
2794:
2790:
2786:
2778:
2774:
2770:
2765:
2761:
2754:
2751:
2746:
2743:
2740:
2737:
2734:
2730:
2721:
2718:
2715:
2712:
2709:
2706:
2703:
2695:
2690:
2687:
2683:
2675:
2671:
2666:
2658:
2645:
2639:
2636:
2630:
2610:
2607:
2604:
2596:
2577:
2574:
2571:
2567:
2563:
2560:
2554:
2531:
2528:
2522:
2502:
2482:
2459:
2453:
2431:
2428:
2424:
2403:
2395:
2391:
2388:
2368:
2364:
2360:
2356:
2352:
2348:
2344:
2339:
2323:
2319:
2296:
2292:
2269:
2265:
2242:
2238:
2214:
2211:
2207:
2198:
2191:
2179:
2176:
2172:
2168:
2165:
2161:
2157:
2154:
2150:
2146:
2143:
2139:
2134:
2114:
2111:
2106:
2103:
2100:
2097:
2094:
2090:
2085:
2082:
2079:
2074:
2071:
2068:
2065:
2062:
2058:
2053:
2045:
2041:
2037:
2032:
2028:
2021:
2018:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1991:
1981:
1976:
1973:
1969:
1961:
1960:
1956:
1955:
1940:
1937:
1934:
1931:
1926:
1923:
1919:
1911:
1897:
1894:
1891:
1888:
1883:
1880:
1876:
1868:
1867:
1863:
1862:
1861:
1859:
1855:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1813:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1757:
1754:
1750:
1740:
1723:
1720:
1714:
1688:
1685:
1682:
1662:
1643:
1640:
1634:
1626:
1622:
1618:
1614:
1596:
1593:
1589:
1580:
1576:
1572:
1568:
1564:
1556:
1552:
1548:
1544:
1540:
1536:
1532:
1529:(A,A) + (3 ×
1528:
1524:
1520:
1516:
1515:
1514:
1508:
1500:
1497:
1494:
1491:
1487:
1483:
1480:
1477:
1474:
1470:
1466:
1463:
1460:
1457:
1453:
1449:
1446:
1443:
1440:
1436:
1420:
1417:
1414:
1408:
1404:
1400:
1394:
1390:
1386:
1381:
1371:
1365:
1359:
1348:
1345:
1343:
1340:
1339:
1338:
1329:
1326:
1323:
1320:
1316:
1312:
1309:
1306:
1303:
1299:
1295:
1292:
1289:
1286:
1282:
1278:
1275:
1272:
1269:
1265:
1249:
1246:
1237:
1234:
1231:
1228:
1224:
1220:
1217:
1214:
1211:
1207:
1203:
1200:
1197:
1194:
1190:
1186:
1183:
1180:
1177:
1173:
1157:
1154:
1151:
1142:
1137:Mismatch = -1
1136:
1133:
1130:
1129:
1128:
1122:Mismatch = -1
1121:
1118:
1115:
1114:
1113:
1111:
1110:edit distance
1093:
1089:
1084:
1077:
1073:
1070:
1069:
1068:
1060:
1057:
1051:
1048:
1045:
1044:
1039:
1036:
1033:
1029:
1025:
1022:
1018:
1014:
1011:
1009:
1008:
1005:
998:
996:
993:
990:
986:
983:
980:
977:
974:
970:
966:
963:
960:
957:
953:
950:
948:
946:
945:
942:
936:
933:
930:
929:
928:
922:
919:
916:
915:
914:
907:
905:
902:
899:
895:
892:
889:
886:
883:
879:
875:
872:
869:
866:
862:
859:
857:
855:
854:
851:
848:
840:
837:
834:
830:
826:
823:
820:
816:
814:
812:
811:
808:
802:
799:
796:
795:
794:
787:
784:
781:
777:
773:
770:
767:
763:
761:
759:
758:
755:
748:
746:
744:
742:
740:
738:
736:
733:
729:
726:
724:
722:
720:
718:
716:
714:
711:
707:
704:
702:
700:
698:
696:
694:
692:
689:
685:
682:
680:
678:
676:
674:
672:
670:
667:
663:
660:
658:
656:
654:
652:
650:
648:
645:
641:
638:
636:
634:
632:
630:
628:
626:
623:
619:
616:
614:
612:
610:
608:
606:
604:
601:
597:
593:
590:
587:
584:
581:
578:
575:
572:
569:
565:
562:
559:
556:
553:
550:
547:
545:
543:
542:
539:
535:
528:
525:
524:
523:
505:
499:
496:
495:
494:
492:
483:
480:
477:
476:
475:
473:
459:
447:
445:
443:
441:
439:
437:
435:
433:
429:
426:
424:
422:
420:
418:
416:
414:
412:
408:
405:
403:
401:
399:
397:
395:
393:
391:
387:
384:
382:
380:
378:
376:
374:
372:
370:
366:
363:
361:
359:
357:
355:
353:
351:
349:
345:
342:
340:
338:
336:
334:
332:
330:
328:
324:
321:
319:
317:
315:
313:
311:
309:
307:
303:
300:
298:
296:
294:
292:
290:
288:
285:
282:
278:
275:
272:
269:
266:
263:
260:
258:
256:
255:
252:
240:
238:
237:DNA sequences
234:
224:
221:
217:
212:
208:
204:
201:
197:
193:
189:
165:
162:
156:
149:
147:
144:
140:
122:
119:
113:
106:
104:
101:
97:
94:
91:
87:
80:
75:
66:
63:
55:
45:
41:
35:
32:This article
30:
21:
20:
3733:Suffix array
3704:
3639:Aho–Corasick
3550:Lee distance
3424:
3415:
3400:by removing
3387:
3356:
3349:
3306:
3302:
3292:
3275:
3271:
3265:
3238:
3232:
3222:
3197:
3193:
3187:
3142:
3138:
3128:
3109:
3105:
3095:
3068:
3047:10 September
3045:. Retrieved
3036:
3011:
3007:
2934:
2922:
2902:
2895:
2884:
2869:
2865:
2861:
2669:
2667:
2664:
2415:
2401:
2393:
2389:
2386:
2366:
2362:
2358:
2354:
2350:
2346:
2342:
2196:
2194:
2189:
2177:
2174:
2170:
2166:
2163:
2159:
2155:
2152:
2148:
2144:
2141:
2137:
2132:
1853:
1811:
1741:
1624:
1620:
1616:
1612:
1578:
1574:
1570:
1560:
1550:
1546:
1542:
1538:
1534:
1530:
1526:
1522:
1518:
1512:
1506:
1415:
1402:
1398:
1392:
1388:
1384:
1377:
1369:
1363:
1356:
1335:
1243:
1152:
1148:
1140:
1125:
1106:
1091:
1087:
1082:
1066:
1058:
1055:
1037:
1003:
994:
981:
940:
926:
912:
903:
890:
849:
845:
838:
806:
792:
785:
753:
536:
533:
520:
503:
487:
469:
457:
249:
230:
227:Introduction
187:
185:
58:
49:
33:
3743:Suffix tree
3194:Kibernetika
2945:distortions
1577:and column
1407:gap penalty
1353:Gap penalty
1134:Indel = -10
1079:candidates.
103:performance
3834:Categories
3462:Biostrings
3145:(1): 4–6.
2988:References
2930:scan lines
2593:using the
2412:Complexity
2392:(i > 0
2361:(i > 0
2353:(i > 0
1119:Indel = -1
1075:sequence).
207:nucleotide
143:Worst-case
100:Worst-case
3402:excessive
3214:123081024
3200:: 81–88.
3112:: 18–31.
3087:429634761
2941:real-time
2798:−
2744:−
2674:recursion
2608:×
2575:
2365:j > 0
2195:Once the
2098:−
2072:−
2011:−
1999:−
1938:∗
1895:∗
1834:…
1792:…
1671:Θ
1131:Match = 1
1116:Match = 0
497:Match: +1
461:12345678
194:used in
192:algorithm
3418:May 2017
3341:23624407
3309:: 1746.
3257:13381535
2951:See also
2345:(A) j ←
2169:(A)
1549:(A,G) +
1545:(T,C) +
1541:(T,A) +
1537:(G,G) +
1525:(G,G) +
1521:(A,C) +
1382:. Here,
1092:G-ATTACA
1088:GCAT-GCG
511:G-ATTACA
508:GCATG-CG
466:G-ATTACA
463:GCATG-CG
3809:Sorting
3779:Parsing
3499:Strings
3396:Please
3388:use of
3332:3638164
3311:Bibcode
3179:4500555
3147:Bibcode
3028:5420325
1739:time).
233:strings
203:protein
38:Please
3339:
3329:
3255:
3212:
3177:
3170:427531
3167:
3085:
3075:
3026:
2926:pixels
2347:length
2343:length
2178:length
2173:j = 1
2167:length
2162:i = 1
2156:length
2151:j = 0
2145:length
2140:i = 0
1864:Basis:
1856:. The
1567:matrix
1347:BLOSUM
286:
190:is an
3772:Other
3728:DAFSA
3695:BLAST
3253:S2CID
3210:S2CID
2351:while
1563:array
1553:(C,T)
472:indel
200:align
89:Class
3763:Trie
3753:Rope
3337:PMID
3175:PMID
3083:OCLC
3073:ISBN
3049:2014
3024:PMID
2719:<
2707:<
2495:and
2402:else
2387:else
2349:(B)
2257:and
1623:and
1565:(or
1533:) +
1401:and
530:not.
474:)):
186:The
3404:or
3327:PMC
3319:doi
3280:doi
3243:doi
3202:doi
3165:PMC
3155:doi
3114:doi
3016:doi
2700:max
2572:log
2515:is
2394:and
2373:, B
2367:and
2363:and
2190:max
2184:, B
2171:for
2160:for
2149:for
2138:for
1985:max
1677:min
1467:−3
1450:−4
1342:PAM
1313:−1
1296:−1
1279:−1
1221:−1
1204:−1
1187:−1
967:−2
927:Y:
913:X:
876:−2
827:−1
774:−1
594:−7
205:or
198:to
42:to
3836::
3335:.
3325:.
3317:.
3305:.
3301:.
3276:26
3274:.
3251:.
3239:21
3237:.
3231:.
3208:.
3196:.
3173:.
3163:.
3153:.
3143:69
3141:.
3137:.
3110:20
3108:.
3104:.
3081:.
3057:^
3022:.
3012:48
3010:.
2996:^
2859:.
2390:if
2359:if
2355:or
2175:to
2164:to
2153:to
2142:to
1659:.
1569:)
1501:8
1495:−3
1492:−4
1489:T
1484:0
1478:−5
1475:−3
1472:C
1464:−5
1458:−1
1455:G
1447:−3
1444:−1
1441:10
1438:A
1433:T
1430:C
1427:G
1424:A
1413:.
1391:,
1330:4
1327:−1
1324:−1
1321:−1
1318:T
1307:−1
1304:−1
1301:C
1293:−1
1287:−1
1284:G
1276:−1
1273:−1
1267:A
1262:T
1259:C
1256:G
1253:A
1238:1
1235:−1
1232:−1
1229:−1
1226:T
1215:−1
1212:−1
1209:C
1201:−1
1195:−1
1192:G
1184:−1
1181:−1
1175:A
1170:T
1167:C
1164:G
1161:A
1031:A
1026:1
1020:T
1015:G
991:−2
988:A
975:−1
972:G
964:−1
954:C
900:−2
897:A
884:−1
881:G
873:−1
863:C
835:−1
832:G
817:G
782:−1
779:G
764:G
734:−7
731:A
712:−6
709:C
690:−5
687:A
668:−4
665:T
646:−3
643:T
624:−2
621:A
602:−1
599:G
591:−6
588:−5
585:−4
582:−3
579:−2
576:−1
566:G
431:A
410:C
389:A
368:T
347:T
326:A
305:G
279:G
3491:e
3484:t
3477:v
3431:)
3425:(
3420:)
3416:(
3412:.
3394:.
3343:.
3321::
3313::
3307:3
3286:.
3282::
3259:.
3245::
3216:.
3204::
3198:4
3181:.
3157::
3149::
3122:.
3116::
3089:.
3051:.
3030:.
3018::
2847:}
2844:)
2839:j
2835:B
2831:,
2826:i
2822:A
2818:(
2815:S
2812:+
2807:k
2804:,
2801:1
2795:i
2791:F
2787:,
2784:)
2779:j
2775:B
2771:,
2766:i
2762:A
2758:(
2755:S
2752:+
2747:1
2741:j
2738:,
2735:h
2731:F
2727:{
2722:j
2716:k
2713:,
2710:i
2704:h
2696:=
2691:j
2688:i
2684:F
2670:d
2646:.
2643:)
2640:n
2637:m
2634:(
2631:O
2611:m
2605:n
2581:)
2578:n
2568:/
2564:n
2561:m
2558:(
2555:O
2535:)
2532:n
2529:m
2526:(
2523:O
2503:m
2483:n
2463:)
2460:1
2457:(
2454:O
2432:j
2429:i
2425:F
2406:j
2398:i
2383:j
2379:i
2375:j
2371:i
2324:j
2320:B
2297:i
2293:A
2270:j
2266:B
2243:i
2239:A
2215:m
2212:n
2208:F
2197:F
2186:j
2182:i
2118:)
2115:d
2112:+
2107:j
2104:,
2101:1
2095:i
2091:F
2086:,
2083:d
2080:+
2075:1
2069:j
2066:,
2063:i
2059:F
2054:,
2051:)
2046:j
2042:B
2038:,
2033:i
2029:A
2025:(
2022:S
2019:+
2014:1
2008:j
2005:,
2002:1
1996:i
1992:F
1988:(
1982:=
1977:j
1974:i
1970:F
1941:i
1935:d
1932:=
1927:0
1924:i
1920:F
1898:j
1892:d
1889:=
1884:j
1881:0
1877:F
1854:B
1840:m
1837:,
1831:,
1828:0
1825:=
1822:j
1812:A
1798:n
1795:,
1789:,
1786:0
1783:=
1780:i
1758:j
1755:i
1751:F
1727:)
1724:m
1721:n
1718:(
1715:O
1695:)
1692:}
1689:m
1686:,
1683:n
1680:{
1674:(
1647:)
1644:m
1641:n
1638:(
1635:O
1625:m
1621:n
1617:B
1613:A
1597:j
1594:i
1590:F
1579:j
1575:i
1571:F
1551:S
1547:S
1543:S
1539:S
1535:S
1531:d
1527:S
1523:S
1519:S
1498:0
1481:9
1461:7
1411:d
1403:b
1399:a
1395:)
1393:b
1389:a
1387:(
1385:S
1310:1
1290:1
1270:1
1218:1
1198:1
1178:1
1038:X
1034:0
1023:1
1012:T
995:0
982:0
978:1
961:0
951:G
904:Y
891:X
887:1
870:0
860:G
839:1
824:0
786:X
771:0
573:0
563:C
560:G
557:T
554:A
551:C
548:G
276:C
273:G
270:T
267:A
264:C
261:G
169:)
166:n
163:m
160:(
157:O
126:)
123:n
120:m
117:(
114:O
65:)
59:(
54:)
50:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
