Indeterminates in London

Today my masters student Joel Helling presented our joint work, Constructing an Indeterminate String from its Associated Graph,  co-authored with P.J. Ryan, W.F. Smyth, at the LSD & LAW 2017 conference. This work started with the visit of W.F. Smyth at CSU Channel Islands in March 2016 – see here, when Joel, Bill and I started working on an initial algorithm designed by Joel; this algorithm computed a labeling for a graph such that any two nodes that shared an edge would also share a label, and would not share a label otherwise. Of course, the easy way to do this is to assign each edge a unique label; but there are better ways of doing it, in the sense that fewer labels may be required (for example, imagine a clique: then a single label would do it). This problem is directly related to indeterminate strings; strings that arise in bio-informatics, where certain positions may consist of several possible symbols. For example, {a,b}ab{a,b,c}{b,c}a, where the first position is not determined (it could be a or b), the second position is a, the third b, the fourth is again not determined (it could be a or b or c), etc. Such strings are well suited to represent genetic
information which often contains “noise”. The paper is now accepted for publication in Elsevier’s journal of Theoretical Computer Science,  as well as presented by Joel at the conference.

I would like to express my gratitude to the British Royal Society for awarding us an exchange grant, CSU Channel Islands / King’s College London, which financed the trip of Joel Helling.

CI Facebook post.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *