RESUMEN
High-throughput experimental screening techniques have resulted in a large number of biological network data such as protein-protein interactions (PPI) data. The analysis of these data can enhance our understanding of cellular processes. PPI network alignment is one of the comparative analysis methods for analyzing biological networks. Research on PPI networks can identify conserved subgraphs and help us to understand evolutionary trajectories across species. Some evolutionary algorithms have been proposed for coping with PPI network alignment, but most of them are limited by the lower search efficiency due to the lack of the priori knowledge. In this paper, we propose a memetic algorithm, denoted as MeAlgn, to solve the biological network alignment by optimizing an objective function which introduces topological structure and sequence similarities. MeAlign combines genetic algorithm with a local search refinement. The genetic algorithm is to find interesting alignment solution regions, and the local search is to find optimal solutions around the regions. The proposed algorithm first develops a coarse similarity score matrix for initialization and then it uses a specific neighborhood heuristic local search strategy to find an optimal alignment. In MeAlign, the information of topological structure and sequence similarities is used to guide our mapping. Experimental results demonstrate that our algorithm can achieve a better mapping than some state-of-the-art algorithms and it makes a better balance between the network topology and nodes sequence similarities.
Asunto(s)
Biología Computacional/métodos , Secuenciación de Nucleótidos de Alto Rendimiento/métodos , Modelos Genéticos , Mapeo de Interacción de Proteínas/métodos , Alineación de Secuencia/métodos , Algoritmos , Animales , Drosophila melanogaster/genética , Humanos , Ratones , Saccharomyces cerevisiae/genéticaRESUMEN
This paper presents a novel matching method of vessels in 3D reconstruction of heart vessel. The directed binary tree was used to describe the topological structure of heart vessel tree's skeleton. Based on topological property and epipolar property, the branch-points and end-points of each branch level could be automatically matched along the direction of blood stream. Thereupon it is easy to couple the corresponding vessels segments of two angiograms projected in different directions. The 3D heart vessel tree was successfully reconstructed from clinic coronary angiograms, which validates the presented method.
Asunto(s)
Humanos , Algoritmos , Simulación por Computador , Angiografía Coronaria , Métodos , Enfermedad Coronaria , Diagnóstico , Diagnóstico por Imagen , Vasos Coronarios , Patología , Procesamiento de Imagen Asistido por Computador , Imagenología Tridimensional , Métodos , Reconocimiento de Normas Patrones Automatizadas , MétodosRESUMEN
Topological description and matching are committed steps for three-dimensional reconstruction of vessel tree from two angiograms. Binary tree is proposed to describe the two-dimensional vessel tree. "Node Weight" and "Similar Node" are defined in order to get better description. Vessel segments in two images are matched by the preorder traversal of the binary trees, and the method is proved fast and accurate.
Asunto(s)
Humanos , Algoritmos , Angiografía , Métodos , Simulación por Computador , Procesamiento de Imagen Asistido por Computador , Métodos , Imagenología Tridimensional , Métodos , Modelos Biológicos , Reconocimiento de Normas Patrones Automatizadas , Métodos , Intensificación de Imagen Radiográfica , MétodosRESUMEN
This paper presents a method for estimating three-dimensional (3D) motion of coronary arteries from single-plane X-ray angiogram sequences on two views. Firstly, original images are preprocessed and two-dimensional (2D) vessel skeletons are extracted. 2D motion estimation is performed along the skeletons in two images. Then geometrical transformation matrix between views is obtained based on perspective projection model for X-ray angiography system, and 3D coordinate of spatial points are calculated. The 3D motion estimation and reconstruction algorithm is applied along the two image sequences to accomplish 3D reconstruction of vessel skeletons and motion vectors between consecutive time instants. Its effectiveness has been demonstrated on clinical single-plane coronary artery angiograms and potential errors are discussed.
Asunto(s)
Humanos , Algoritmos , Angiografía Coronaria , Métodos , Enfermedad Coronaria , Diagnóstico por Imagen , Electrocardiografía , Imagenología Tridimensional , Métodos , Movimiento , Interpretación de Imagen Radiográfica Asistida por ComputadorRESUMEN
This paper presents an approach for estimating the non-rigid motion of coronary arteries using digital angiographic images. Displacement vectors of vessel points are obtained by finding points correspondences in two successive frames. Smoothness of motion field and vessel deformation measurement are considered in matching, and unmatched regions are also dealt with in the fact that the vessel after deformation may have different size with its original station. The search strategy for optimal matching is carried out using dynamic programming (DP) so that computing cost is reduced. Results of this motion estimation method applied to synthetic and clinical images have shown that the method is accurate, with a root mean square error about one pixel for simulated data. For the case of actual X-ray coronary angiographic images, visual inspection of the detected pairs of points shows that the results are very encouraging.