1
$\begingroup$

My Masters program is focused on formal methods such as SAT solving and constraint programming. I am interested in applying such techniques to problems in sequence alignment and sequence analysis, areas that have been dominated by statistical methods.

So can you give me examples of some research problems suitable to be approached as constraints satisfaction problems?

Note: By constraint programming I also include more flexible paradigms like weighted constraint programming, where a solution may violate some of the constraints.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean optimization? In any case I guess you either have to state your problem clearly and what you want to do. Moreover, this question is not really suitable for this forum. You can ask this in CS-SE. $\endgroup$
    – WYSIWYG
    Commented Sep 2, 2014 at 4:35
  • $\begingroup$ I mean a problem that can be modeled by specifying a set of constraints and specifying relations between these constraints. Optimization is a special case and is more related to weighted constraints problem (then we are optimizing for a minimum violation weight) $\endgroup$
    – Anas Elghafari
    Commented Sep 2, 2014 at 10:25
  • $\begingroup$ As for asking this on CS-SE: I disagree, my question is not about constraint programming. It is about what problems in bioinformatics (in particular sequence alignment) can be tackled as a constraints problem. The people who would know this best are people working in biology. $\endgroup$
    – Anas Elghafari
    Commented Sep 2, 2014 at 10:30

1 Answer 1

Reset to default
1
$\begingroup$

First read how local and global alignment differ from each other. Then decide an objective function, i.e. how to measure the similarity between two sequences? Maybe use Hamming distance? Or Levenshtein distance? After this the optimization part probably comes out quite naturally.

Be sure to check the existing softwares. Easy things have been tried out already. (And by the way, for some reason biologists call n-grams as k-mers.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Well, I am in the middle of project on using HMMs for alignment, and have read the basics. But the problems I have read about (aligning two sequences for functional analysis and allowing for nucleotide insertion/deletion) does not seem to be suitable for modelling with constraints. So I am asking to see if there are other problems that might be better suitable for that. $\endgroup$
    – Anas Elghafari
    Commented Sep 2, 2014 at 12:42
  • $\begingroup$ The closest thing I've seen that may be suitable for constraints approach is the use to transformational grammar for long-distance dependencies. But even there I am not very sure it can be framed as CSP. $\endgroup$
    – Anas Elghafari
    Commented Sep 2, 2014 at 12:45
  • 1
    $\begingroup$ Try reading this article: plosone.org/article/… Any help? $\endgroup$
    – ggggg
    Commented Sep 2, 2014 at 12:51
  • $\begingroup$ Thanks, maybe. One will have to look at the systems/tools mentioned in the article to see if there are any that are constraints-based (rather than statistics based) or at least incorporate constraints in some way.If so then that would be a good candidate for constraints programming project. $\endgroup$
    – Anas Elghafari
    Commented Sep 3, 2014 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .