Definition
Smith–Waterman–Gotoh
Smith–Waterman–Gotoh (SWG) is a string comparison algorithm that uses local sequence alignment to identify the strongest matching regions between two sequences of characters. It combines the Smith–Waterman approach with Gotoh’s efficient affine gap penalty method, making it useful for identifying partial similarities when text contains insertions, deletions or additional characters.
Key Takeaways
- Smith–Waterman–Gotoh identifies the strongest locally aligned portions of two strings rather than requiring a complete end-to-end match.
- It uses affine gap penalties to distinguish between opening a gap and extending an existing gap.
- The algorithm can help identify partial similarities in names, company names and other text fields.
- A high alignment score does not necessarily mean two records represent the same person or organisation.
- WinPure AdaptiveMatch™ enables Smith–Waterman–Gotoh to be combined with other matching algorithms at individual-column level.
Smith-Waterman-Gotoh Similarity Calculator
Compare two text values using local sequence alignment with affine gap penalties.
These values contain a strong local match.
Smith-Waterman-Gotoh finds the best matching region within two values and applies affine gap penalties, making it useful when one value contains additional or missing text.
WinPure AdaptiveMatch™ can combine Smith-Waterman-Gotoh with other matching algorithms, thresholds and field-level logic to improve matching across real-world data.
What Is the Smith–Waterman–Gotoh Algorithm?
The Smith–Waterman–Gotoh (SWG) algorithm is a string similarity algorithm that uses local sequence alignment to identify the strongest matching regions between two strings, even when characters are missing, added or different.
Originally developed for biological sequence comparison, it uses affine gap penalties to handle insertions and deletions, making it useful for fuzzy matching, data deduplication and record linkage.
For example, it can identify the similarity between ACME Technologies Ltd and ACME Technologies by recognising their shared text.
In WinPure Clean & Match Enterprise v12, Smith–Waterman–Gotoh is available through AdaptiveMatch™, allowing users to combine it with other fuzzy, phonetic and exact matching algorithms for more flexible data matching.
How Does Smith–Waterman–Gotoh Work?
The Smith–Waterman–Gotoh algorithm compares two strings character by character to identify the strongest matching sequence within them. Rather than requiring the entire strings to match, it uses local sequence alignment to find regions of high similarity.
The algorithm works through four key steps:
- Character Comparison: Each character is compared against characters in the other string, assigning positive scores for matches and penalties for mismatches.
- Gap Penalties: Insertions and deletions are evaluated using affine gap penalties, which distinguish between opening a new gap and extending an existing one.
- Alignment Scoring: A scoring matrix is calculated to identify the highest-scoring local alignment between the two strings.
- Best Match Identification: The algorithm identifies the strongest matching region, producing an alignment score that reflects the similarity under the selected scoring rules.
For example, comparing “Global Technologies Ltd” with “Global Technologies” allows the algorithm to identify the shared text without requiring the additional company suffix to match.
This approach makes Smith–Waterman–Gotoh particularly useful for fuzzy string matching and data deduplication, especially when records contain partial names, additional words or inconsistent text.
Understanding Local Sequence Alignment
Local sequence alignment is the process of identifying the most similar regions within two strings, rather than comparing every character from beginning to end.
Unlike global alignment, which attempts to align entire strings, local alignment focuses on the strongest matching sections, allowing unrelated characters or additional text to be excluded.
| String | Before shared region | Best shared region | After shared region |
|---|---|---|---|
| International Business Solutions Ltd | International | Business Solutions | Ltd |
| Business Solutions | — | Business Solutions | — |
The Smith–Waterman–Gotoh algorithm can identify Business Solutions as the strongest matching region, even though the first string contains additional words.
This makes local sequence alignment particularly useful for fuzzy matching, data deduplication and record linkage, where customer names, company names and other text fields may contain extra information, missing characters or variations.
However, a strong local match does not always indicate that two records represent the same entity. For reliable results, local alignment is often combined with other matching conditions and data attributes.
The Smith–Waterman–Gotoh Formula
The Smith–Waterman–Gotoh algorithm calculates string similarity using a scoring system that rewards matching characters while applying penalties for mismatches, insertions and deletions.
Its key feature is the use of affine gap penalties, which distinguish between opening a new gap and extending an existing one.
The gap penalty is commonly expressed as:
G(k) = go + (k − 1)ge
| Gap length (k) | Linear penalty (3 per character) | Affine penalty (opening 5; extension 1) |
|---|---|---|
| 1 | 3 | 5 |
| 2 | 6 | 6 |
| 3 | 9 | 7 |
| 4 | 12 | 8 |
Where:
- G(k) = Total penalty for a gap of length k
- go = Gap opening penalty
- ge = Gap extension penalty
- k = Number of characters in the gap
For example, with a gap opening penalty of 5 and a gap extension penalty of 1, a gap containing three characters would receive a penalty of:
G(3) = 5 + (3 − 1) × 1 = 7
The algorithm combines these penalties with character match and mismatch scores in dynamic programming matrices to identify the highest-scoring local alignment.
Unlike algorithms such as Levenshtein Distance, which calculate the minimum number of edits needed to transform one complete string into another, Smith–Waterman–Gotoh focuses on finding the strongest matching region.
This makes it particularly useful for partial string matching, fuzzy matching and data deduplication, where records may contain additional or missing text.
A Worked Smith–Waterman–Gotoh Example
To understand how the Smith–Waterman–Gotoh algorithm works in practice, consider two company names that contain similar information but differ in length.
- String 1: Global Technologies Ltd
- String 2: Global Technologies
Although the first string includes the additional suffix Ltd, both share the same core company name.
Step 1: Compare the Characters
The algorithm compares characters from both strings, assigning scores based on whether they match or differ.
For this example, we’ll use the following scoring configuration:
| Scoring condition | Score |
|---|---|
| Matching character | +2 |
| Mismatching character | −1 |
| Gap opening penalty | −5 |
| Gap extension penalty | −1 |
Step 2: Identify the Strongest Local Alignment
Smith–Waterman–Gotoh calculates a scoring matrix to identify the highest-scoring matching region.
In this example, the strongest alignment is:
String 1: GLOBAL TECHNOLOGIES
String 2: GLOBAL TECHNOLOGIES
The additional LTD suffix is excluded because local sequence alignment does not require every character in both strings to be matched.
Step 3: Calculate the Alignment Score
The shared text contains 19 characters, including the space. In this illustrative configuration, spaces are treated as characters; preprocessing choices may change the result.
With a match reward of +2 per character and no mismatches or gaps within the selected alignment:
Alignment Score = 19 × 2 = 38
This represents a perfect local alignment for the shared portion of the two strings under the chosen scoring configuration.
Step 4: Interpret the Result
The high alignment score indicates that the two company names contain a strongly matching sequence, despite the additional suffix.
However, a high local alignment score does not automatically confirm that two records represent the same organisation. Additional attributes, such as addresses, company registration numbers or contact details, may be needed to establish a reliable match.
In WinPure AdaptiveMatch™, Smith–Waterman–Gotoh can be combined with other fuzzy and exact matching conditions to help identify potential duplicate records across business datasets.
Smith–Waterman vs Smith–Waterman–Gotoh
The Smith–Waterman and Smith–Waterman–Gotoh algorithms both use local sequence alignment to identify the strongest matching regions between two strings. The main difference lies in how they handle gaps caused by inserted or deleted characters.
Smith–Waterman identifies optimal local alignments using dynamic programming. Gotoh’s enhancement efficiently computes alignments with affine gap penalties, allowing the algorithm to distinguish between opening a new gap and extending an existing one.
This is particularly useful when comparing strings containing missing words, additional characters or variations in spelling.
| Feature | Smith–Waterman | Smith–Waterman–Gotoh |
|---|---|---|
| Alignment method | Local alignment | Local alignment |
| Gap penalties | Traditionally linear | Affine |
| Gap opening and extension | Typically same cost per character | Different penalties |
| Handling consecutive gaps | Linear penalty | More flexible affine penalty |
| Computational complexity | O(m × n) with linear gaps | O(m × n) with affine gaps |
| Primary application | Sequence similarity | Sequence similarity with flexible gap scoring |
| Data matching applications | Partial string matching | Partial matching with insertions and deletions |
Why Does Gotoh’s Enhancement Matter?
Consider two strings where one contains several additional characters. A linear gap penalty assigns the same cost to each inserted or deleted character, while an affine gap penalty typically applies a higher cost to opening a gap and a smaller cost to extending it.
This allows Smith–Waterman–Gotoh to treat a continuous sequence of missing characters differently from several separate gaps, potentially producing more meaningful alignments.
For fuzzy string matching and data deduplication, this provides additional flexibility when comparing customer names, company names and other text fields containing variations.
In WinPure Clean & Match Enterprise v12, Smith–Waterman–Gotoh is available through AdaptiveMatch™, enabling users to select it for appropriate fields alongside other matching algorithms.
Smith–Waterman–Gotoh vs Levenshtein Distance
Both Smith–Waterman–Gotoh and Levenshtein Distance are string comparison algorithms used to identify similarities between text values. However, they take different approaches to measuring similarity.
Levenshtein Distance calculates the minimum number of single-character insertions, deletions and substitutions required to transform one complete string into another. In contrast, Smith–Waterman–Gotoh uses local sequence alignment to identify the strongest matching region within two strings, applying affine gap penalties to handle insertions and deletions.
| Feature | Smith–Waterman–Gotoh | Levenshtein Distance |
|---|---|---|
| Comparison method | Local sequence alignment | Edit distance |
| Primary focus | Strongest matching region | Entire string |
| Insertions and deletions | Affine gap penalties | Single edit cost per character |
| Additional text | Can exclude unrelated sections | Counts additional characters as edits |
| Output | Alignment score | Edit distance |
| Best suited for | Partial strings and shared sequences | Spelling variations and typographical errors |
| Typical applications | Partial name matching, record linkage | Data cleansing, deduplication, typo detection |
Example: Comparing Company Names
Consider the following two company names:
- String 1: Global Technologies Ltd
- String 2: Global Technologies
Using Levenshtein Distance, the additional four characters, including the space before Ltd, contribute to an edit distance of 4.
Using Smith–Waterman–Gotoh, the algorithm can identify Global Technologies as the strongest matching region without penalising the additional suffix outside the selected local alignment.
Which Algorithm Should You Use?
Levenshtein Distance is generally useful for identifying spelling mistakes, missing characters and minor variations across complete strings.
Smith–Waterman–Gotoh is particularly useful when strings contain substantial shared sections but differ in length or include additional information.
Neither algorithm is universally better. The most appropriate choice depends on the characteristics of the data and the type of differences being identified.
With WinPure AdaptiveMatch™, organisations can select different matching algorithms for individual data fields, combining local sequence alignment, edit distance, fuzzy matching and phonetic methods to create more flexible and accurate matching rules.
Smith–Waterman–Gotoh vs Jaro-Winkler
Both Smith–Waterman–Gotoh and Jaro-Winkler are string similarity algorithms used in fuzzy matching and data deduplication. However, they use different techniques to identify similarities between text values.
Smith–Waterman–Gotoh uses local sequence alignment to identify the strongest matching regions between two strings, making it useful when text contains additional words, missing sections or inserted characters.
Jaro-Winkler, on the other hand, measures character similarity and transpositions, giving additional weight to strings that share a common prefix. This makes it particularly effective for comparing personal names and identifying typographical errors.
| Feature | Smith–Waterman–Gotoh | Jaro-Winkler |
|---|---|---|
| Matching approach | Local sequence alignment | Character similarity and transpositions |
| Primary focus | Strongest matching region | Overall character similarity |
| Common prefixes | No special prefix weighting | Rewards matching prefixes |
| Insertions and deletions | Affine gap penalties | Reflected in character matching |
| Transposed characters | Treated through alignment scoring | Explicitly considers transpositions |
| Additional text | Can exclude unrelated sections | Generally reduces similarity |
| Output | Alignment score | Similarity score between 0 and 1 |
| Best suited for | Partial strings and shared text sequences | Names, spelling variations and typing errors |
Example: Comparing Customer Names
Consider two customer names:
- String 1: Jonathan Smith
- String 2: Jonathon Smith
Jaro-Winkler is well suited to this comparison because the names share many characters, have a common prefix and contain a minor spelling variation.
Smith–Waterman–Gotoh can also identify substantial matching regions, but its result depends on the selected match, mismatch and gap penalties.
Now consider a different example:
- String 1: International Business Solutions Ltd
- String 2: Business Solutions
In this case, Smith–Waterman–Gotoh can identify Business Solutions as a strong local alignment despite the additional words in the first string.
Jaro-Winkler compares the strings more broadly, so the additional text generally reduces its similarity score.
Which Algorithm Is Better for Data Matching?
Jaro-Winkler is often a good choice for matching personal names, correcting minor spelling variations and identifying transposed characters.
Smith–Waterman–Gotoh is particularly useful when comparing strings that contain shared sequences alongside additional or missing text.
Neither algorithm is universally more accurate. Their effectiveness depends on the data, scoring configuration and matching requirements.
With WinPure AdaptiveMatch™, users can apply Smith–Waterman–Gotoh, Jaro-Winkler and other matching algorithms to individual columns, allowing each field to be compared using an appropriate method.
When Is Smith–Waterman–Gotoh Useful?
The Smith–Waterman–Gotoh algorithm is particularly useful when comparing text values that contain substantial matching sections but differ in length, formatting or additional information. Its ability to identify strong local alignments makes it valuable for fuzzy string matching, data deduplication and record linkage.
Common applications include:
- Company Name Matching: Identifying similarities between organisation names containing additional words, abbreviations or legal suffixes, such as Global Technologies Ltd and Global Technologies.
- Customer Record Deduplication: Detecting potential duplicate records where names or other text fields contain missing, additional or inconsistent information.
- Partial String Matching: Recognising shared sequences within longer text values, even when surrounding characters differ.
- CRM Data Cleansing: Identifying potentially related customer or supplier records across databases with inconsistent naming conventions.
- Product Description Matching: Comparing product names or descriptions that share distinctive text sequences but contain additional identifiers or wording.
- Data Integration and Migration: Helping identify corresponding records across systems that store names and descriptions in different formats.
When Should You Choose Smith–Waterman–Gotoh?
Smith–Waterman–Gotoh is worth considering when partial text similarity is more important than an exact character-by-character comparison.
However, local alignment can sometimes produce misleadingly strong matches between unrelated records that share common words or short sequences. For reliable results, it should be combined with appropriate similarity thresholds and other matching conditions.
In WinPure Clean & Match Enterprise v12, AdaptiveMatch™ allows Smith–Waterman–Gotoh to be applied to selected data fields alongside other fuzzy, phonetic and exact matching algorithms, helping organisations build more flexible and reliable data matching strategies.
Limitations and False Matches
Although the Smith–Waterman–Gotoh algorithm is effective at identifying partial string similarities, it has limitations that should be considered when using it for fuzzy matching and data deduplication.
Because the algorithm focuses on the strongest matching region rather than the entire string, it can sometimes produce high alignment scores for records that share common text but represent different entities.
Key limitations include:
- False Positive Matches: Unrelated records containing common words or character sequences may produce strong local alignments.
- Short Matching Sequences: A high-scoring substring does not necessarily indicate that two complete values are similar.
- Sensitivity to Scoring Parameters: Match rewards, mismatch penalties and gap costs can significantly influence alignment results.
- Computational Requirements: Dynamic programming can be more resource-intensive than simpler string comparison algorithms, particularly across large datasets.
- Limited Contextual Understanding: The algorithm compares character sequences rather than understanding the meaning or identity of the underlying data.
Example: A Potential False Match
Consider two company names:
- String 1: Global Financial Services Ltd
- String 2: Global Technology Solutions Ltd
Both contain the word Global and the suffix Ltd. Smith–Waterman–Gotoh may identify these shared sequences as strong local alignments, even though the companies could be entirely unrelated.
How Can False Matches Be Reduced?
False matches can be reduced by selecting appropriate scoring parameters, testing similarity thresholds against representative data and combining multiple matching conditions.
For example, matching company names alongside addresses, registration numbers or other identifying attributes can provide stronger evidence that two records belong to the same organisation.
With WinPure AdaptiveMatch™, users can combine Smith–Waterman–Gotoh with other fuzzy, phonetic and exact matching algorithms across individual fields, helping improve matching reliability while reducing the risk of false positives.
Choosing a Similarity Threshold
Selecting an appropriate similarity threshold is important when using the Smith–Waterman–Gotoh algorithm for fuzzy matching and data deduplication. The threshold determines how closely two strings must align before they are considered a potential match.
Unlike algorithms such as Jaro-Winkler, which produce a similarity score between 0 and 1, Smith–Waterman–Gotoh produces a raw alignment score based on character matches, mismatches and gap penalties. This score may be normalised to a percentage, depending on the software implementation. The normalisation formula must be documented before scores from different datasets or tools are compared.
How Do Similarity Thresholds Affect Matching?
A higher similarity threshold generally produces fewer potential matches, while a lower threshold allows more variations to be identified.
| Threshold approach | Typical behaviour | Consideration |
|---|---|---|
| High | Requires stronger similarity | May miss genuine matches containing substantial variations |
| Medium | Balances similarity and flexibility | Requires testing against representative records |
| Low | Identifies more potential matches | Greater risk of false positives |
There is no universal percentage threshold suitable for every Smith–Waterman–Gotoh implementation. Results depend on the scoring configuration, normalisation method and characteristics of the data.
Best Practices for Selecting a Threshold
- Start with Representative Data: Test the algorithm against examples of genuine matches and unrelated records.
- Evaluate False Positives: Check whether common words or short matching sequences produce misleading results.
- Consider Field Characteristics: Company names, addresses and product descriptions may require different thresholds.
- Combine Matching Conditions: Use additional fields, such as postcodes, email addresses or company identifiers, to improve reliability.
- Review and Refine: Adjust thresholds based on actual matching results rather than relying on a single default setting.
In WinPure Clean & Match Enterprise v12, AdaptiveMatch™ enables users to configure matching algorithms and similarity thresholds at the individual-column level, allowing Smith–Waterman–Gotoh to form part of a broader, more controlled data matching strategy.
Using Smith–Waterman–Gotoh in AdaptiveMatch™
WinPure AdaptiveMatch™, available in WinPure Clean & Match Enterprise v12, enables organisations to apply Smith–Waterman–Gotoh alongside other fuzzy, phonetic and exact matching algorithms, creating more intelligent and flexible data matching rules.
Illustrative AdaptiveMatch™ interface concept showing field-level algorithm selection and company-name matching. The example similarity percentages are illustrative, not measured results.
Rather than relying on a single algorithm across an entire dataset, AdaptiveMatch™ allows users to select the most appropriate matching method for each individual column, based on its data type and matching requirements.
For example, a matching configuration might include:
| Data Field | Matching Algorithm | Purpose |
|---|---|---|
| Company Name | Smith–Waterman–Gotoh | Identify shared text sequences and partial name variations |
| Contact Name | Jaro-Winkler | Detect spelling differences and transposed characters |
| Address | WinPureFuzzy™ | Identify variations in address information |
| Postcode | Exact Match | Compare standardised postcode values |
| Telephone | Exact Match | Compare normalised telephone numbers |
Intelligent Matching with Greater Control
At the heart of AdaptiveMatch™ is WinPure’s Data Type Library, featuring over 120 predefined data types and 13 matching algorithms. This intelligent configuration framework helps users select suitable matching methods while providing control over similarity thresholds, field weighting and matching conditions.
By combining Smith–Waterman–Gotoh with other algorithms, organisations can identify potential duplicates across customer databases, CRM systems and enterprise datasets while reducing reliance on any single similarity measure.
AdaptiveMatch™ brings together algorithm flexibility, intelligent recommendations and WinPure’s re-engineered matching engine, helping organisations build more precise, scalable and effective data matching strategies.
Related reading: Explore the data matching algorithms guide to understand how different comparison methods can be combined. For a closer look at field-level algorithm selection, see WinPure’s AdaptiveMatch™ overview when published.
Conclusion: Smarter String Matching with Smith–Waterman–Gotoh
The Smith–Waterman–Gotoh algorithm provides a flexible approach to fuzzy string matching by identifying strong local alignments and handling insertions and deletions through affine gap penalties.
Its effectiveness depends on suitable scoring parameters, carefully tested similarity thresholds and supporting record attributes. In WinPure AdaptiveMatch™, it can be combined with other algorithms to create field-specific matching rules that help identify potential duplicates and improve data quality.
Discover Smarter Data Matching with WinPure
Put Smith–Waterman–Gotoh and other powerful matching algorithms to work with WinPure AdaptiveMatch™. Identify duplicates, improve data quality and match records with greater flexibility. Try WinPure free for 30 days. No credit card required.
Frequently Asked Questions About Smith–Waterman–Gotoh
Smith–Waterman–Gotoh is a string similarity algorithm that identifies the strongest matching regions between two strings using local sequence alignment. It applies affine gap penalties to handle insertions and deletions, making it useful for fuzzy matching, data deduplication and record linkage.
The algorithm compares characters between two strings, assigning rewards for matches and penalties for mismatches and gaps. It uses dynamic programming to identify the highest-scoring local alignment, allowing it to recognise similarities even when strings contain additional or missing text.
Both algorithms perform local sequence alignment. Gotoh’s enhancement provides an efficient way to calculate affine gap penalties, applying different costs to opening and extending gaps. This allows more flexible handling of consecutive insertions and deletions.
Affine gap penalties assign one cost to opening a gap and another to extending it. This allows the algorithm to distinguish between a single continuous gap and several separate gaps, potentially producing more meaningful sequence alignments.
Levenshtein Distance measures the minimum number of single-character edits required to transform one complete string into another. Smith–Waterman–Gotoh identifies the strongest matching region within two strings, making it particularly useful for partial text matching.
Neither algorithm is universally better. Smith–Waterman–Gotoh is useful for identifying shared text sequences within longer strings, while Jaro-Winkler is often effective for comparing names containing spelling variations and transposed characters. The best choice depends on the data and matching requirements.
There is no universal similarity threshold because alignment scores depend on the scoring parameters and any normalisation method used. Thresholds should be tested against representative datasets to balance genuine matches against false positives.
Yes. Smith–Waterman–Gotoh can help identify potential duplicate records containing partial names, additional words or inconsistent text. For reliable deduplication, it is best combined with other matching conditions and identifying attributes.
No. Smith–Waterman–Gotoh is a deterministic sequence alignment algorithm based on dynamic programming. It does not learn from training data, although it can be incorporated into broader data matching systems that use machine learning or AI.
Yes. Smith–Waterman–Gotoh is one of the matching algorithms available through AdaptiveMatch™ in WinPure Clean & Match Enterprise v12. Users can apply it to individual data fields alongside other fuzzy, phonetic and exact matching algorithms.
Share this article
