Peter Leven
Institute for Computer Science
Albert-Ludwigs-Universität Freiburg
The talk deals with a new approach to compute multi sequence alignments. After an introduction to sequence alignment problems we report on two methods, that are based on the segment selection: The first one is a Greedy method and the second is based on linear programming. Our new approach is based on a regular language; for describing and solving the segment selection problem we introduce the ``synchronizing regular language with shuffle and intersection operator''. The relationship to bipartite matching problems is given. Preliminary results indicate, how the segment selection problem can be reduced to bipartite matching problems. The formal refinement and the development of an effective procedure will be part of future investigations.