^March April – 2009 ^May

It is well known that the string edit distance and the alignment of strings coincide, while the alignment of trees differs from the tree edit distance. In this talk, we recall various constraints on directed acyclic graphs that allow for a unique (up to isomorphism) representation, called the path multiplicity representation, and present a new method for the alignment of trees and directed acyclic graphs that exploits the path multiplicity representation to produce a meaningful optimal alignment in polynomial time.

Formal grammars are constraint systems that made up of rules that define the permissible arrangements of tokens (words) in a language. Using grammars we are able to also represent mobile genetic elements (MGE), assemblages of genes and protein interaction sites that can move between molecules in a bacterial cell and often move between organisms through conjugation facilitated by plasmids (horizontal gene transfer). MGEs are the principal cause in the evolution of strains of bacteria that are simultaneously resistant to multiple antibiotics as resistance genes accumulate in MGEs. I will present a novel method to computationally “read” MGEs in bacterial DNA using a context sensitive grammar but deterministic parser. I will also present how the grammar can be used to produce high-fidelity annotations of high level structures such as MGEs and two applications: large-scale surveys and a new method for gene discovery which is complementary to contemporary discovery methods.

Dr. Guy Tsafnat is the head of the Translational Bioinformatics group at the Centre for Health Informatics at UNSW – Australia’s largest and oldest centre for medical informatics research. The Translational Bioindformatics group researchers the role of computational biology in clinical decision support systems. Prior to academia, for 8 years he has conducted research in machine learning in the software industry both in Sydney and in Silicon Valley, California. His PhD and later research are in computational biology and translational bioinformatics, and is focused on computational discovery.

We present a novel approach for model based segmentation of gray-scale images of highly degraded historical documents. Given a training set of characters (of a certain letter), we construct a small set of shape models that cover most of the training set's shape variance. For each gray-scale image of a respective degraded character, we construct a custom made shape prior using those fragments of the shape models that best fit the character's boundary. Experiments show that our method achieves very accurate results both in segmentation of highly degraded characters and both in recognition