SequenceAlignment
SequenceAlignment[s1,s2]
finds an optimal alignment of sequences of elements in the strings, lists or biomolecular sequences s1 and s2, and yields a list of successive matching and differing sequences.
Details and Options
- SequenceAlignment[s1,s2] gives a list of the form {seg1,seg2,…} where each segi is either a single string or sequence of list elements u, representing a matching segment, or a pair {u1,u2}, representing segments that differ between the si.
- The following options can be given:
-
GapPenalty 0 additional cost for each alignment gap IgnoreCase False whether to ignore case of letters in strings MergeDifferences True whether to combine adjacent differences Method "Global" alignment algorithm to be used SimilarityRules Automatic rules for similarities between elements - SequenceAlignment attempts to find an alignment that maximizes the total similarity score.
- SequenceAlignment by default finds a global Needleman–Wunsch alignment of the complete strings or lists s1 and s2.
- With the option setting Method->"Local", it finds a local Smith–Waterman alignment.
- For sufficiently similar strings or lists, local and global alignment methods give the same result.
- SequenceAlignment also supports methods "AlignByLongestCommonSequence" and "AlignByLongestSubsequences", provided GapPenalty, MergeDifferences and SimilarityRules are all set to their respective defaults.
- Whereas the "Global" and "Local" methods both maximize a similarity score, "AlignByLongestCommonSequence" maximizes the number of characters or list elements common to both sequences.
- "AlignByLongestSubsequences" is effectively a divide-and-conquer heuristic approximation to aligning by the longest common (not necessarily contiguous) sequence, trading accuracy for speed. When sequences are fairly close, the alignment quality will be good, outperforming the other methods by up to two orders of magnitude in speed.
- With the default setting SimilarityRules->Automatic, each match between two elements contributes 1 to the total similarity score, while each mismatch, insertion, or deletion contributes -1.
- Various named similarity matrices are supported, as specified in the notes for SimilarityRules.
Examples
open all close allBasic Examples (2)
Globally align two similar strings:
SequenceAlignment["abcXabcXabc", "abcYabcYabc"]Global alignment of two instances of BioSequence:
SequenceAlignment[BioSequence["DNA", "CGGAGT"], BioSequence["DNA", "CGTAGT"]]Options (8)
GapPenalty (1)
IgnoreCase (1)
SequenceAlignment treats string input as case sensitive:
SequenceAlignment["abcdefgHIJKlmn", "abCDEfgHIjklmn"]With IgnoreCaseTrue, SequenceAlignment will convert both strings to lowercase before aligning:
SequenceAlignment["abcdefgHIJKlmn", "abCDEfgHIjklmn", IgnoreCase -> True]MergeDifferences (1)
Method (3)
Default global alignment of two strings:
SequenceAlignment["abcXXabcXabc", "abcabcYYYabc"]SequenceAlignment["abcXXabcXabc", "abcabcYYYabc", Method -> "Global"]Local alignment of the same strings:
SequenceAlignment["abcXXabcXabc", "abcabcYYYabc", Method -> "Local"]str1 = BioSequence[Entity["Gene", {"HBA1", {"Species" -> "HomoSapiens"}}]]["SequenceString"];
str2 = BioSequence[Entity["Gene", {"HBA2", {"Species" -> "HomoSapiens"}}]]["SequenceString"];The "AlignByLongestCommonSequence" method maximizes the number of characters or list elements common to both sequences:
matchCount[align_] := StringLength[StringJoin@@Cases[align, _String]]matchCount@SequenceAlignment[str1, str2]matchCount@SequenceAlignment[str1, str2, Method -> "AlignByLongestCommonSequence"]Take two texts, remove their diacritics and convert to lowercase:
textA = ExampleData[{"Text", "UNHumanRightsIrish"}]//RemoveDiacritics//ToLowerCase;
textB = ExampleData[{"Text", "UNHumanRightsScottishGaelic"}]//RemoveDiacritics//ToLowerCase;The "AlignByLongestSubsequences" method can be significantly faster for similar sequences, but it can give a notably smaller set of matching characters:
matchCount[align_] := StringLength[StringJoin@@Cases[align, _String]]matchCount@SequenceAlignment[textA, textB]//AbsoluteTimingmatchCount@SequenceAlignment[textA, textB, Method -> "AlignByLongestSubsequences"]//AbsoluteTimingSimilarityRules (2)
Align two short protein sequences:
SequenceAlignment["FTFTALILLAVAV", "FTALLLAAV"]Assigning a negative score to the deletion of "V" gives a different alignment:
SequenceAlignment["FTFTALILLAVAV", "FTALLLAAV", SimilarityRules -> {{"V", ""} -> -10}]Align with type-specific similarity rules that align degenerate letters:
SequenceAlignment[BioSequence["DNA", "AAATTCCAAANNTNCCAAAA"], BioSequence["DNA", "GGTTCC"], SimilarityRules -> "SimilarDegenerateBases"]Without the degenerate similarity rules, a perfect degenerate alignment is missed:
SequenceAlignment[BioSequence["DNA", "AAATTCCAAANNTNCCAAAA"], BioSequence["DNA", "GGTTCC"]]Applications (4)
This gives the global alignment of two similar strings:
SequenceAlignment["That's one small step for man", "That's one small step for a man"]This shows the difference between global and local string alignment:
SequenceAlignment["One fish two fish", "One fish two fish red fish blue fish"]SequenceAlignment["One fish two fish", "One fish two fish red fish blue fish", Method -> "Local"]Obtain reference BRCA1 gene sequences for a human and a chimpanzee:
human = Entity["Gene", {"BRCA1", {"Species" -> "HomoSapiens"}}]["ReferenceSequence"];
chimp = Entity["Gene", {"BRCA1", {"Species" -> "PanTroglodytes"}}]["ReferenceSequence"];Check that their lengths are similar:
StringLength /@ {human, chimp}Align them using the default ("Global") method, using ByteCount to check the size of the result:
ByteCount[align1 = SequenceAlignment[human, chimp]]//AbsoluteTimingThe "Local" method is slower, though it gives a more concise result:
ByteCount[align2 = SequenceAlignment[human, chimp, Method -> "Local"]]//AbsoluteTimingAlign using the longest sequence common to the pair:
ByteCount[align3 = SequenceAlignment[human, chimp, Method -> "AlignByLongestCommonSequence"]]//AbsoluteTimingMethod "AlignByLongestSubsequences" is the fastest in this case and gives the smallest result:
ByteCount[align4 = SequenceAlignment[human, chimp, Method -> "AlignByLongestSubsequences"]]//AbsoluteTimingMatching segments are close in total length, with the alignment using the longest common sequence having the largest matching part:
matchCount[align_] := StringLength[StringJoin@@Cases[align, _String]]Map[matchCount, {align1, align2, align3, align4}]Obtain two Scandinavian language versions of the UN Universal Declaration of Human Rights:
UNHRD = ExampleData[{"Text", "UNHumanRightsDanish"}]//RemoveDiacritics//ToLowerCase;
UNHRS = ExampleData[{"Text", "UNHumanRightsSwedish"}]//RemoveDiacritics//ToLowerCase;
Map[StringLength, {UNHRD, UNHRS}]Align using both the default and longest common subsequences methods and compare by byte count:
ByteCount[align1 = SequenceAlignment[UNHRD, UNHRS]]//AbsoluteTimingByteCount[align2 = SequenceAlignment[UNHRD, UNHRS, Method -> "AlignByLongestSubsequences"]]//AbsoluteTimingThe global method has around 60% of the characters in the matching sections:
matchCount[align_] := StringLength[StringJoin@@Cases[align, _String]]matchCount[align1]The faster heuristic method also manages to get nearly 57% of the characters in the matching parts:
matchCount[align2]Possible Issues (1)
When aligning nested lists, a list at level one can be a common element of the input lists:
a = {{1}, {}};SequenceAlignment[a, a]Or a list at level one may denote a difference between the two input lists:
b = {1};c = {};SequenceAlignment[b, c]As the two outputs are identical, the output cannot be used to disambiguate the two cases:
% === %%Neat Examples (1)
Compare two very similar genes:
SequenceAlignment[BioSequence[Entity["Gene", {"HBA1", {"Species" -> "HomoSapiens"}}]], BioSequence[Entity["Gene", {"HBA2", {"Species" -> "HomoSapiens"}}]]]Use Diff to see the difference graphically:
Diff[BioSequence[Entity["Gene", {"HBA1", {"Species" -> "HomoSapiens"}}]], BioSequence[Entity["Gene", {"HBA2", {"Species" -> "HomoSapiens"}}]]]
An Elementary Introduction to the Wolfram LanguageText
Wolfram Research (2008), SequenceAlignment, Wolfram Language function, https://reference.wolfram.com/language/ref/SequenceAlignment.html (updated 2024).
CMS
Wolfram Language. 2008. "SequenceAlignment." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2024. https://reference.wolfram.com/language/ref/SequenceAlignment.html.
APA
Wolfram Language. (2008). SequenceAlignment. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/SequenceAlignment.html