logo móvil
Contáctanos

Un ptas para el problema de estructuras de consenso bajo la distancia euclidiana al cuadrado

Autores: Li, Shuai Cheng; Ng, Yen Kaow; Zhang, Louxin

Idioma: Inglés

Editor: MDPI

Año: 2008

Descargar PDF

Acceso abierto

Artículo científico
2008

Un ptas para el problema de estructuras de consenso bajo la distancia euclidiana al cuadrado


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Agrupamiento
Bioinformática
Fragmentos estructurales
Distancia euclidiana
Esquema de aproximación de tiempo polinómico
PTAS

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 21

Citaciones: Sin citaciones


Descripción
En este documento consideramos un problema básico de agrupamiento que tiene usos en bioinformática. A es una secuencia de puntos en un espacio 3D, donde es un número natural fijo. Dos fragmentos estructurales y son equivalentes si y solo si bajo alguna rotación y traslación . Consideramos la distancia entre dos fragmentos estructurales como la suma de la distancia euclidiana al cuadrado entre todos los puntos correspondientes de los fragmentos estructurales. Dado un conjunto de fragmentos estructurales, consideramos el problema de encontrar (o menos) fragmentos estructurales , de modo que se minimice la suma de las distancias entre cada uno de ellos y su fragmento estructural más cercano en . En este documento mostramos un esquema de aproximación en tiempo polinómico (PTAS) para el problema a través de una estrategia de muestreo simple.

Otros recursos que podrían interesarte

Temas Virtualpro