Difference between revisions of "AA/Seminar"

From LRDE

Line 10: Line 10:
   
 
* Friday 14 October 14:00: [https://www.lix.polytechnique.fr/Labo/Sarah.BERKEMER/ Sarah Berkemer]: ''Compositional properties of alignments''
 
* Friday 14 October 14:00: [https://www.lix.polytechnique.fr/Labo/Sarah.BERKEMER/ Sarah Berkemer]: ''Compositional properties of alignments''
  +
** Alignments, i.e., position-wise comparisons of two or more strings or ordered lists are of utmost practical importance in computational biology and a host of other fields, including historical linguistics and emerging areas of research in the Digital Humanities. The problem is well-known to be computationally hard as soon as the number of input strings is not bounded. Due to its practical importance, a huge number of heuristics have been devised, which have proved very successful in a wide range of applications. Alignments nevertheless have received hardly any attention as formal, mathematical structures. Here, we focus on the compositional aspects of alignments, which underlie most algorithmic approaches to computing alignments. We also show that the concepts naturally generalize to finite partially ordered sets and partial maps between them that in some sense preserve the partial orders. As a consequence of this discussion we observe that alignments of even more general structure, in particular graphs, are essentially characterized by the fact that the restriction of alignments to a row must coincide with the corresponding input graphs. Pairwise alignments of graphs are therefore determined completely by common induced subgraphs. In this setting alignments of alignments are well-defined, and alignments can be decomposed recursively into subalignments. This provides a general framework within which different classes of alignment algorithms can be explored for objects very different from sequences and other totally ordered data structures.
** Alignments, i.e., position-wise comparisons of two or more strings or
 
ordered lists are of utmost practical importance in computational
 
biology and a host of other fields, including historical linguistics and
 
emerging areas of research in the Digital Humanities. The problem is
 
well-known to be computationally hard as soon as the number
 
of input strings is not bounded. Due to its practical importance, a huge
 
number of heuristics have been devised, which have proved very
 
successful in a wide range of applications. Alignments nevertheless have
 
received hardly any attention as formal, mathematical structures. Here,
 
we focus on the compositional aspects of alignments, which underlie most
 
algorithmic approaches to computing alignments. We also show that the
 
concepts naturally generalize to finite partially ordered sets and
 
partial maps between them that in some sense preserve the partial
 
orders. As a consequence of this discussion we observe that alignments
 
of even more general structure, in particular graphs, are
 
essentially characterized by the fact that the restriction of alignments
 
to a row must coincide with the corresponding input graphs. Pairwise
 
alignments of graphs are therefore determined completely by common
 
induced subgraphs. In this setting alignments of alignments are
 
well-defined, and alignments can be decomposed recursively into
 
subalignments. This provides a general framework within which different
 
classes of alignment algorithms can be explored for objects very
 
different from sequences and other totally ordered data structures.
 
 
** Online at https://meet.lrde.epita.fr/seminar-lre_aa-20221014
 
** Online at https://meet.lrde.epita.fr/seminar-lre_aa-20221014
   

Revision as of 18:27, 4 October 2022

Seminar "Automata and Applications"

The seminar of the research group Automata and Applications is held every 2-3 weeks, usually online. It is open to the public.

The languages of the seminar are French and English. Talks may be given, and questions asked, in any of the two languages.

If you want to participate in the seminar, or if you want to propose a talk, send an email to the organizer.

Upcoming Talks

  • Friday 14 October 14:00: Sarah Berkemer: Compositional properties of alignments
    • Alignments, i.e., position-wise comparisons of two or more strings or ordered lists are of utmost practical importance in computational biology and a host of other fields, including historical linguistics and emerging areas of research in the Digital Humanities. The problem is well-known to be computationally hard as soon as the number of input strings is not bounded. Due to its practical importance, a huge number of heuristics have been devised, which have proved very successful in a wide range of applications. Alignments nevertheless have received hardly any attention as formal, mathematical structures. Here, we focus on the compositional aspects of alignments, which underlie most algorithmic approaches to computing alignments. We also show that the concepts naturally generalize to finite partially ordered sets and partial maps between them that in some sense preserve the partial orders. As a consequence of this discussion we observe that alignments of even more general structure, in particular graphs, are essentially characterized by the fact that the restriction of alignments to a row must coincide with the corresponding input graphs. Pairwise alignments of graphs are therefore determined completely by common induced subgraphs. In this setting alignments of alignments are well-defined, and alignments can be decomposed recursively into subalignments. This provides a general framework within which different classes of alignment algorithms can be explored for objects very different from sequences and other totally ordered data structures.
    • Online at https://meet.lrde.epita.fr/seminar-lre_aa-20221014

Previous Seminars

  • Friday 30 September 14:00: Florian Renkin: Transformations d’ω-automates pour la synthèse de systèmes réactifs
    • La synthèse vise à produire un système correct à partir de spécifications. Une approche pour résoudre ce problème consiste à traduire la spécification en un jeu de parité dont la stratégie gagnante encode le système. Dans cet exposé nous verrons deux méthodes permettant de produire des automates de parité. La première s’appuie sur l’amélioration et la combinaison de procédures nouvelles ou existantes. La seconde est un algorithme de Casares et al. apportant une garantie d’optimalité du résultat. Dans un deuxième temps, nous verrons comment nous réduisons le système obtenu. Deux types de réductions seront abordées. La première permet d’obtenir un résultat optimal mais pas la seconde qui privilégie le temps de traitement.
    • Online at https://meet.lrde.epita.fr/seminar-lre_aa-20220930 and in salle KB / Apprentissage 1