Download Multi-alignment of Genomes - ALGGEN

ALGGEN
Grupo de Algorítmica y Genética:
• Dep. Lenguajes y Sistema Informáticos
Universidad Politécnica de Catalunya
• CEPBA-IBM Research Institute
http://www.lsi.upc.es/~alggen
ALGGEN
Diseño de aplicaciones bioinformáticas
• Docencia: LEPA
• Investigación: MALGEN, PROMO, MREPATT
Integrantes:
• Colaboraciones con investigadores “in lab”
• Estudiantes de informática realizando su PFC
• Estudiantes de doctorado
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
Image and interface
accgc…….cttgc
...tccgg……ccaac...
Matching
Unicos
Maximales
MALGEN: Preview of four genomes
Chlamydophila pneumoniae AR39: 1.247420bps
Chlamydia pneumoniae: 1.247.805
Chlamidia muridarum: 1.084.689bps
Chlamidia trachomatis:1057413bps








MALGEN: Preview of two genomes
Pyrococcus abyssis: 1.790.334
Pyrococcus horikoshu: 1.763.341 bps
MALGEN: Coste
Algoritmo MALGEN:
• Se construye el Suffix-tree del más corto,
• Se recorre el árbol mientras se van leyendo los otros
genomas
Tiempo lineal respecto la suma de las longitudes de los
genomas.
Espacio lineal respecto al genoma más corto.
ALGGEN: algorithmics and genetics group
PROMO: Cromosomas, genes i`promotores
DNA:
DNA:
Promotor
(hambre mañana verano)
DNA:
Gen
(Tostadas con mantequilla i mermelada)
PROMO: Predicción de los sitios de union
(binding sites)
DNA:
DNA:
Promotor
(hambre mañana verano
Gen
(Tostadas con mantequilla y mermelada)
DNA:
Se pueden predecir?
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
ALGGEN: algorithmics and genetics group
PROMO: Coste
PROMO:
• Crea automáticamente las matrices para la especie
seleccionada,
• Realiza la búsqueda en una o más cadenas de los factores
• y de las zonas similares que no llevan un factor asociado.
Tiempo de construcción del autómata de búsqueda es grande
Tiempo de búsqueda es lineal respecto la longitud de las
cadenas
ALGGEN: algorithmics and genetics group
MREPATT
Busca repeticiones consecutivas de uno o más
patrones (y de su complementario) en uno o más
genomas.
Tiempo de búsqueda es lineal respecto la longitud de
los genomas.
ALGGEN
Los colaboradores:
Mario Huerta: MALGEN (Dr. J. Rozas)
Domènec Farré: PROMO (Dra. M. Albà)
Romà Roset: MREPATT (Dr. J.A. Subirana)
http://www.lsi.upc.es/~alggen:
Roman Roset
Dr. Xavier Messeguer