Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

toConciseAlignmentString is non-deterministic #907

Open
sbliven opened this issue Dec 7, 2020 · 0 comments
Open

toConciseAlignmentString is non-deterministic #907

sbliven opened this issue Dec 7, 2020 · 0 comments

Comments

@sbliven
Copy link
Member

sbliven commented Dec 7, 2020

In #906, @Vidishab18 showed some test cases using AlignmentTools.toConciseAlignmentString can produce different results depending on HashMap iteration order.

The method takes an alignment map (a way of representing a pairwise alignment as a map between residue indices) and outputs a string representation. The representation is not unique. For instance "1>2>3>2 4>3" and "4>3 1>2>3>2" are the same alignment. Likewise, "1>2>1" and "2>1>2" are the same alignment. Outputs potentially hinge on the enumeration order of the underlying map.

Possible solutions:

  1. Create a canonical form (e.g. sorted some way). I'm not sure whether this is feasible; general graph canonization is computationally hard, but perhaps the special structure of alignment graphs gives an obvious order
  2. Use a SortedMap (TreeMap) internally. This should make it deterministic, although perhaps not in a simple form
  3. Merge Fixing flaky test in AlignmentToolsTest.java #906, which apparently fixes the tests even though it leaves the function itself unchanged.

The method was intended as a concise human-readable output of the map, so the order doesn't really matter. Option 2 appears to be the simplest solution. Performance on this method is not critical.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant