1 package edu.uci.iotproject.test;
3 import edu.uci.iotproject.comparison.seqalignment.AlignmentPricer;
4 import edu.uci.iotproject.comparison.seqalignment.SequenceAlignment;
5 import org.junit.Before;
8 import java.util.function.ToIntBiFunction;
9 import java.util.function.ToIntFunction;
11 import static org.junit.Assert.assertTrue;
12 import static org.junit.Assert.fail;
15 * Tests the implementation of {@link SequenceAlignment}.
17 * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
18 * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
20 public class SequenceAlignmentTest {
22 private char[] lowercaseVowels;
23 private char[] lowercaseConsonants;
25 private Character[] meanChars;
26 private Character[] nameChars;
29 * Cost function for the alignment of letters in the example execution of the sequence alignment algorithm in
30 * Kleinberg's and Tardos' "Algorithm Design", where 'mean' and 'name' are aligned.
32 private ToIntBiFunction<Character, Character> kleinbergExampleAlignmentCostFunc;
35 * Cost function for the alignment of letters with gaps in the example execution of the sequence alignment algorithm
36 * in Kleinberg's and Tardos' "Algorithm Design", where 'mean' and 'name' are aligned. Gap cost is set to 2,
37 * regardless of input character.
39 private ToIntFunction<Character> kleinbergExampleGapCostFunc;
42 * Calculates the cost of aligning a letter with another letter or a letter with a gap according to the cost recipe
43 * used in the example in Kleinberg & Tardos.
45 private AlignmentPricer<Character> kleinbergAlignmentPricer;
48 * Executes the sequence alignment algorithm using the cost function defined in the example in Kleinberg & Tardos,
49 * i.e., {@link #kleinbergAlignmentPricer}.
51 private SequenceAlignment<Character> kleinbergSequenceAligner;
54 public void initialize() {
55 // We consider 'y' a vowel for the sake of simplicity.
56 // Note: we assume an all lowercase string!
57 lowercaseVowels = new char[] { 'a', 'e', 'i', 'o', 'u', 'y' };
58 lowercaseConsonants = new char[] { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's',
59 't', 'v', 'w', 'x', 'z' };
60 kleinbergExampleAlignmentCostFunc = (c1, c2) -> {
61 // Unbox to primitive type for the sake of brevity in the statements to follow.
62 final char char1 = c1.charValue();
63 final char char2 = c2.charValue();
65 // If char1 and char2 are the same characters, the cost of aligning them is 0.
66 if (char1 == char2) return 0;
68 final boolean char1IsVowel = isVowel(char1);
69 final boolean char1IsConsonant = isConsonant(char1);
70 final boolean char2IsVowel = isVowel(char2);
71 final boolean char2IsConsonant = isConsonant(char2);
73 // Alignment cost is undefined for non alphabet characters.
74 if (!char1IsVowel && !char1IsConsonant) fail("not an alphabet letter: " + char1);
75 if (!char2IsVowel && !char2IsConsonant) fail("not an alphabet letter: " + char2);
77 // If char1 and char2 are both vowels or both consonants, the cost is 1.
78 if (char1IsVowel && char2IsVowel || char1IsConsonant && char2IsConsonant) return 1;
80 // If one of char1 and char2 is a consonant, while the other is a vowel, the cost is 3.
83 // The cost of a gap is 2, regardless of what letter is aligned with the gap.
84 kleinbergExampleGapCostFunc = c -> 2;
86 // char[] -> Character[] conversion courtesy of https://stackoverflow.com/a/27690990/1214974
87 meanChars = "mean".chars().mapToObj(c -> (char)c).toArray(Character[]::new);
88 nameChars = "name".chars().mapToObj(c -> (char)c).toArray(Character[]::new);
90 kleinbergAlignmentPricer = new AlignmentPricer<>(kleinbergExampleAlignmentCostFunc,
91 kleinbergExampleGapCostFunc);
93 kleinbergSequenceAligner = new SequenceAlignment<>(kleinbergAlignmentPricer);
97 public void kleinbergExampleOptAlignmentCostShouldBe6() {
98 // Cost of the optimal alignment of the two words
99 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(meanChars, nameChars);
100 final int expectedAlignmentCost = 6;
101 String msg = String.format("Kleinberg example: computed opt != expected opt (computed=%d expected=%d)",
102 optAlignmentCost, expectedAlignmentCost);
103 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
108 public void meanAlignedWithEmptyStringShouldBe8() {
109 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(meanChars, new Character[0]);
110 // 'mean' aligned with the empty string equals paying four gap costs, so total cost is: 4 * 2 = 8.
111 final int expectedAlignmentCost = 8;
112 String msg = String.format("'mean' aligned with empty string: computed opt != expected opt (computed=%d expected=%d)",
113 optAlignmentCost, expectedAlignmentCost);
114 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
118 public void mAlignedWithNameShouldBe6() {
120 * Note: this also uses the cost function specified in Kleinberg & Tardos.
121 * Best alignment should be:
124 * This should have a cost of 3 * gapCost = 6
126 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'm' }, nameChars);
127 final int expectedAlignmentCost = 6;
128 String msg = String.format("'m' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
129 optAlignmentCost, expectedAlignmentCost);
130 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
134 public void meAlignedWithNameShouldBe4() {
136 * Note: this also uses the cost function specified in Kleinberg & Tardos.
137 * Best alignment should be:
140 * This should have a cost of 2 * gapCost = 4
142 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'm', 'e' }, nameChars);
143 final int expectedAlignmentCost = 4;
144 String msg = String.format("'me' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
145 optAlignmentCost, expectedAlignmentCost);
146 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
147 // Check that order of arguments doesn't matter
148 final int optAlignmentCostReversed = kleinbergSequenceAligner.calculateAlignment(nameChars, new Character[] { 'm', 'e' });
149 msg = "'me' aligned with 'name': different order of arguments unexpectedly produced different result";
150 assertTrue(msg, optAlignmentCostReversed == optAlignmentCost && optAlignmentCostReversed == expectedAlignmentCost);
154 public void ameAlignedWithNameShouldBe2() {
156 * Note: this also uses the cost function specified in Kleinberg & Tardos.
157 * Best alignment should be:
160 * This should have a cost of 1 * gapCost = 2
162 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'a', 'm', 'e' }, nameChars);
163 final int expectedAlignmentCost = 2;
164 String msg = String.format("'ame' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
165 optAlignmentCost, expectedAlignmentCost);
166 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
170 public void fameAlignedWithNameShouldBe1() {
172 * Note: this also uses the cost function specified in Kleinberg & Tardos.
173 * Best alignment should be:
176 * This should have a cost of 1 * consonantMatchedWithConsonantCost = 1
178 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'f', 'a', 'm', 'e' },
180 final int expectedAlignmentCost = 1;
181 String msg = String.format("'fame' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
182 optAlignmentCost, expectedAlignmentCost);
183 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
187 public void nameAlignedWithNameShouldBe0() {
189 * Note: this also uses the cost function specified in Kleinberg & Tardos.
190 * Best alignment should be:
193 * This should have a cost of 0.
195 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'n', 'a', 'm', 'e' },
197 final int expectedAlignmentCost = 0;
198 String msg = String.format("'name' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
199 optAlignmentCost, expectedAlignmentCost);
200 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
204 public void emanAlignedWithNameShouldBe6() {
206 * Note: this also uses the cost function specified in Kleinberg & Tardos.
207 * Best alignment should be:
217 * This should have a cost of 2 * gapCost + 2 * consonantMatchedWithConsonantCost = 2 * 2 + 2 * 1 = 6.
219 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'e', 'm', 'a', 'n' },
221 final int expectedAlignmentCost = 6;
222 String msg = String.format("'eman' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
223 optAlignmentCost, expectedAlignmentCost);
224 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
228 public void naemAlignedWithNameShouldBe4() {
230 * Note: this also uses the cost function specified in Kleinberg & Tardos.
231 * Best alignment should be:
241 * This should have a cost of 2 * gapCost = 4.
243 final int optAlignmentCost = kleinbergSequenceAligner.calculateAlignment(new Character[] { 'n', 'a', 'e', 'm' },
245 final int expectedAlignmentCost = 4;
246 String msg = String.format("'naem' aligned with 'name': computed opt != expected opt (computed=%d expected=%d)",
247 optAlignmentCost, expectedAlignmentCost);
248 assertTrue(msg, optAlignmentCost == expectedAlignmentCost);
253 * Checks if {@code letter} is a lowercase vowel. Note: for simplicity, 'y' is considered a <em>vowel</em>.
254 * @param letter A {@code char} expected to be a vowel.
255 * @return {@code true} if {@code letter} is a vowel, {@code false} otherwise.
257 private boolean isVowel(char letter) {
258 for (char vowel : lowercaseVowels) {
259 if (letter == vowel) {
267 * Checks if {@code letter} is a lowercase consonant. Note: for simplicity, 'y' is considered a <em>vowel</em>.
268 * @param letter A {@code char} expected to be a consonant.
269 * @return {@code true} if {@code letter} is a consonant, {@code false} otherwise.
271 private boolean isConsonant(char letter) {
272 for (char consonant : lowercaseConsonants) {
273 if (letter == consonant) {