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
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
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.
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.