← 输入框|github.com|刷新
Skip to content

toConciseAlignmentString is non-deterministic #907

Open

Description

@sbliven

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.

Activity

  1. added a commit that references this issue on Dec 7, 2020
    1fe5059
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions