Dr Wayne Haynes will be visiting St Andrews on Wed 28 September; his talk (abstract below) will take place at 3pm in Maths lecture theatre C — Please note the change of venue.
Biological network alignment has the potential to be as useful as sequence alignment has in relation to learning about biology, evolution, and disease. Although about two dozen network alignment algorithms have been proposed, none as yet have proven to fulfill this potential, due to many shortcomings. Some of these shortcomings include: lack of knowledge about how to best use network topology to recover biological information (EC? S3? Graphlets? Spectral?); how to balance biological information such as sequence against topological information; confusion in the literature between an alignment algorithm and the objective function used to guide the alignment, as well as confusion between how to produce the alignment vs. how to measure it’s quality post-alignment; lack of a good multiple network alignment algorithm; lack of an effective method to eliminate the 1-to-1 nature of global network alignment, since 1-to-1 mappings are not faithful to the evolutionary relationship between proteins; and finally, due to the NP-complete nature of the problem, a lack of knowledge about how far we are from producing the best alignments possible?
In this talk, I will introduce a novel method that already solves some of these problems and for which there is a clear path towards solving all of the others listed above, and more. We clearly delineate the measure(s) M that measure the quality of an alignment, from the algorithm S that searches the space of all alignments looking for good ones according to M. This allows us to directly compare many measures M. We also demonstrate that our new algorithm S outperforms all existing algorithms by all the various measures that we’ve tried.