CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs.

For biological applications, sequence alignment is an important strategy to analyze DNA and protein sequences. Multiple sequence alignment is an essential methodology to study biological data, such as homology modeling, phylogenetic reconstruction and etc. However, multiple sequence alignment is a NP-hard problem. In the past decades, progressive approach has been proposed to successfully align multiple sequences by adopting iterative pairwise alignments. Due to rapid growth of the next generation sequencing technologies, a large number of sequences can be produced in a short period of time. When the problem instance is large, progressive alignment will be time consuming. Parallel computing is a suitable solution for such applications, and GPU is one of the important architectures for contemporary parallel computing researches. Therefore, we proposed a GPU version of ClustalW v2.0.11, called CUDA ClustalW v1.0, in this work. From the experiment results, it can be seen that the CUDA ClustalW v1.0 can achieve more than 33× speedups for overall execution time by comparing to ClustalW v2.0.11.

Multiple genome sequences alignment algorithm based on coding regions.

Multiple Sequence Alignment (MSA) is the computational biology tool for facilitating the study of DNA homology, phylogeny determinations and conserved motifs. Many MSA methods have been presented to align protein, DNA, and RNA sequences successfully but not for coding region sequences. Therefore, we propose a heuristic alignment method, CORAL-M, for multiple genome sequences, especially for coding regions. CORAL-M adopts a codon-based probabilistic filtration model and the local optimal alignment solution to align multiple genome sequences in linear time. The experimental results presents that CORAL-M can find more potential function sites than that of other commonly used tools by aligning Enterovirus strains.

Genetic copy number variants in myocardial infarction patients with hyperlipidemia.

BACKGROUND: Cardiovascular disease is the chief cause of death in Taiwan and many countries, of which myocardial infarction (MI) is the most serious condition. Hyperlipidemia appears to be a significant cause of myocardial infarction, because it causes atherosclerosis directly. In recent years, copy number variation (CNV) has been analyzed in genomewide association studies of complex diseases. In this study, CNV was analyzed in blood samples and SNP arrays from 31 myocardial infarction patients with hyperlipidemia. RESULTS: We identified seven CNV regions that were associated significantly with hyperlipidemia and myocardial infarction in our patients through multistage analysis (P<0.001), at 1p21.3, 1q31.2 (CDC73), 1q42.2 (DISC1), 3p21.31 (CDCP1), 10q11.21 (RET) 12p12.3 (PIK3C2G) and 16q23.3 (CDH13), respectively. In particular, the CNV region at 10q11.21 was examined by quantitative real-time PCR, the results of which were consistent with microarray findings. CONCLUSIONS: Our preliminary results constitute an alternative method of evaluating the relationship between CNV regions and cardiovascular disease. These susceptibility CNV regions may be used as biomarkers for early-stage diagnosis of hyperlipidemia and myocardial infarction, rendering them valuable for further research and discussion.

Feature amplified voting algorithm for functional analysis of protein superfamily.

BACKGROUND: Identifying the regions associated with protein function is a singularly important task in the post-genomic era. Biological studies often identify functional enzyme residues by amino acid sequences, particularly when related structural information is unavailable. In some cases of protein superfamilies, functional residues are difficult to detect by current alignment tools or evolutionary strategies when phylogenetic relationships do not parallel their protein functions. The solution proposed in this study is Feature Amplified Voting Algorithm with Three-profile alignment (FAVAT). The core concept of FAVAT is to reveal the desired features of a target enzyme or protein by voting on three different property groups aligned by three-profile alignment method. Functional residues of a target protein can then be retrieved by FAVAT analysis. In this study, the amidohydrolase superfamily was an interesting case for verifying the proposed approach because it contains divergent enzymes and proteins. RESULTS: The FAVAT was used to identify critical residues of mammalian imidase, a member of the amidohydrolase superfamily. Members of this superfamily were first classified by their functional properties and sources of original organisms. After FAVAT analysis, candidate residues were identified and compared to a bacterial hydantoinase in which the crystal structure (1GKQ) has been fully elucidated. One modified lysine, three histidines and one aspartate were found to participate in the coordination of metal ions in the active site. The FAVAT analysis also redressed the misrecognition of metal coordinator Asp57 by the multiple sequence alignment (MSA) method. Several other amino acid residues known to be related to the function or structure of mammalian imidase were also identified. CONCLUSIONS: The FAVAT is shown to predict functionally important amino acids in amidohydrolase superfamily. This strategy effectively identifies functionally important residues by analyzing the discrepancy between the sequence and functional properties of related proteins in a superfamily, and it should be applicable to other protein families.

A polygon model for wireless sensor network deployment with directional sensing areas.

The modeling of the sensing area of a sensor node is essential for the deployment algorithm of wireless sensor networks (WSNs). In this paper, a polygon model is proposed for the sensor node with directional sensing area. In addition, a WSN deployment algorithm is presented with topology control and scoring mechanisms to maintain network connectivity and improve sensing coverage rate. To evaluate the proposed polygon model and WSN deployment algorithm, a simulation is conducted. The simulation results show that the proposed polygon model outperforms the existed disk model and circular sector model in terms of the maximum sensing coverage rate.