1
$\begingroup$

Problem

Imagine I have a list of categorical labels: A A A B C C B B B C C A C C. I want to calculate a numerical measure that characterizes how ordered it is. So perfectly ordered lists, where there is no mixing between labels of different kind, like A A A A B B B B C C C C or C C C C C B B B B B A A A A A and so forth should get a score of e.g. 1. On the other hand, random lists where probability of each next label in a sequence only depends on its overall frequency should get a score of e.g. 0.

Possible approaches

I thought about calculating pairwise distances (e.g. Hamming) between my sequence, random sequences and perfectly ordered sequences of the same length. Then I can use MDS to project them on 2D space and find "order axis" along which I can then calculate distance.

I can also come up with some sort of heuristic measures, like counting the number of different types of labels in a sliding window or for each label in the sequence calculating the distance to the closest label of the same kind.

Can I fit some sort of stochastic process to it and measure its memory? Just a wild idea.

Seems like this should be a trivial problem, but I couldn't find any out-of-the-box solutions.

Context

I have a dataset N_drugs x N_genes. Each drug belongs to a specific functional group - hence the categorical labels. I want to select a subset of genes that will allow the best separation between different functional groups of the drugs. The actual data are vectors of logarithmic changes (treated condition vs non-treated condition) and therefore cosine similarity is the most natural distance metric. So at the end I get a N_drugs x N_drugs distance matrix that I order using hierarchical clustering. Resulting order of labels (functional groups) is what I am trying to evaluate. Hope it makes sense.

Thank you in advance for any comments or suggestions.

Improve this question
$\endgroup$
1
  • $\begingroup$ Are you looking for a measure of entropy? $\endgroup$
    – George Savva
    Commented Oct 25, 2023 at 12:03

1 Answer 1

Reset to default
2
$\begingroup$

You can implement a bubble sort and count how many times you need to swap items before the list is ordered. Call this number n. To find out the number of swaps needed for a random sequence, construct random sequences with the same properties as your real sample, and compute the number of swaps to sort each sequence. Call the maximum number of swaps needed to sort a random sequence N. Your index is then 1 - n/N.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But than the sequence A A A A B B B A B B A B B B A will have a higher score, than say a sequence A A A A B B B B B B B B A A A. What I need is a Runs test but for sequences with more than 2 values: en.wikipedia.org/wiki/Wald%E2%80%93Wolfowitz_runs_test $\endgroup$
    – perlusha
    Commented Nov 6, 2023 at 12:21
  • $\begingroup$ It was your use of "order" that confused that me. My solution is for deeming AAABBBCCCCZZ perfectly ordered. Just to make sure, you would consider BBBAAAZZCCCC perfectly ordered? $\endgroup$
    – Niels Holst
    Commented Nov 7, 2023 at 14:59
  • $\begingroup$ This makes it difficult to find a solution. With 4 letters (A, B, C and Z in my example) there would be 4!=24 different perfect orderings. You would have to measure the distance from the actual sequence to each of these perfect orders; the solution would be the minimum of these 24 distances. How many different letters have you got in your sequences? $\endgroup$
    – Niels Holst
    Commented Nov 7, 2023 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.