filter SPARQL results by number of matches against a query list?

Question

I want to query a database of Gene signatures, where each signature basically consists of a list of gene symbols (Think "Ache", "Bcan", "Gjb1" ...).

I then want to use a list of such gene symbols (say for example "Ache", "Bcan", "Gjb1") as a query list, and get signatures that has a given minimum number of matches against my query list.

Can I / how can I most easily, implement this in SPARQL?

The case of minimum one match, it is easy, that would be (for the mentioned query list of "Ache", "Bcan", "Gjb1"), like so:

SELECT ?signature WHERE { 
    ?signature [some gene-symbol property] ?symbol .
    FILTER (?symbol = STR('Ache') || ?symbol = STR('Bcan') || ?symbol = STR('Gjbl'))
}

... but how to go about for an arbitrary "minimum matches" count, without getting a too convoluted query?

Accepted Answer

2

You can do this using the aggregate support in SPARQL 1.1:

SELECT ?signature WHERE { 
  ?signature [some gene-symbol property] ?symbol .
  FILTER (?symbol IN ("Ache", "Bcan", "Gjbl"))
}
GROUP BY ?signature
HAVING (COUNT(?symbol) > N)

(untested; substitute in your value of N as you see fit)

Lee

link

answered 03 Jan, 16:11

lee
3.1k●1●9
accept rate: 35%

Ah, looks nice! Unfortunately my triplestore (4store) install does not seem to have SPARQL 1.1 support yet ... :/

(03 Jan, 16:22) Samuel Lampa

1

I can't think of any realistic way to do it if limited to SPARQL 1.0 constructs, unfortunately. Switch triple stores? :-)

(03 Jan, 16:24) lee

Well, I'm trying now, with 4 query genes, and the limit (N)=2, by manually (could later be programmed) creating the queries with pairs of match statements, glued together with SPARQL UNIONS. 4s seems to make quite a good job at least for these: 0.048 s, with 7 MTs in the store. Gotta see how it goes with larger numbers though :)

(05 Jan, 09:45) Samuel Lampa

Produced all the permutations in python. Succeeded to query a 7 gene list with min matches set to 4 (takes some 4 seconds, some python processing). A bigger min_matches would cause "argument too long" (I'm executing the SPARQL query on the command line, with 4s-query), so I guess I better give up this idea :)

(05 Jan, 11:23) Samuel Lampa

Answer 2

Ok, had to turn to a combination of SPARQL and Python, to generate the query.

Went for something like this:

def format_subclause(predicate, gene):
    return " ?s tm:%s ?o . FILTER ( ?o = STR('%s') ) " % (predicate, gene)

query = "PREFIX tm: <%s> " % prefix
query += "SELECT ?s ?o WHERE { { "
query += "} UNION {".join([format_subclause(predicate, g) for g in query_genes])
query += "} }"

This will result in all items that match any of the query genes, so in order to filter out only the ones with matches greater than "min_matches", I wrote some more python code, like this:

facts = {} # New python "array"
output = query_4store(query)
for item in output:
    parts = re.split("\s+", item.strip())
    key = parts[0]
    value = parts[1].strip('"')
    # Add only uniqe values to list
    if facts.has_key(key):
        if not value in facts[key]:
            facts[key].append(value)
    else:
        # Create new list
        facts[key] = [value]

# DEBUG CODE START
print "OUTPUT:"
print "-"*80
for fact in facts:
    gene_count = len(facts[fact])
    if gene_count >= min_matches:
        print fact,facts[fact],gene_count
# DEBUG CODE END

(The "<" and ">" in the code examples are actually "<" and ">")

Running the script with "min_matches" set to 51 (the highest number of genes in any item) takes around 2.5 seconds (The triplestore contains around 7 million triples). Seems to be good enough for my use case.

Wanted to document this here although it is not a pure SPARQL solution, in case it can help someone else.

Also, feel free to share your suggestions on how to write the pyhotn code in a more clean way!

filter SPARQL results by number of matches against a query list?

Follow this question

Upcoming Events

Related questions