基于遗传算法和模拟退火算法的DNA多序列比对算法研究

提出了一种基于遗传算法和模拟退火算法的DNA多序列比对算法。针对多序列比对的具体特点 ,指出交叉操作是导致比对计算复杂度提高的原因之一 ,因而在本研究所提出的多序列比对算法中 ,取消了遗传算法中通常采用的交叉操作算子 ,设计了适合多序列比对特点的插入删除算子和合并分离算子 ,同时在多序列比对的总对数评分规则的基础上提出了完全比对块的概念 ,采用了完全比对块加权的个体适应度值评价函数以引导遗传算法寻优局部比对。本研究还引入了基于模拟退火算法的遗传操作算子调用机制 ,以便在避免完全比对块过多的被遗传操作所破坏的同时防止遗传算法陷入局部极小 ,达到兼顾算法寻优质量和效率的目的。最后通过一个DNA多序列比对的算例验证了算法的可行性。     

基于蒙特卡洛的医学图像重建体积计算算法GPU加速研究

目的:确定基于蒙特卡洛算法计算体积的精度及提高其速度,为医学图像的应用领域快速提供可靠的数据。 方法:在FonicsPlan计划系统平台上,实现基于蒙特卡洛方法的体积计算,并使用C++AMP对算法做GPU并行加速,然后对体积计算结果在精度和速度上进行比较分析。 结果:与像素累加法、体元累加法相比,蒙特卡洛算法的准确性最高但其算法用时也最长。通过充分利用计算机的显卡计算性能,可将计算速度平均提高50倍。 结论:经GPU加速后的蒙特卡洛算法在计算体积的速度和精度两方面都能满足临床要求,在医学图像处理及临床诊疗具有较高的应用价值。     

免疫算法的改进及在DNA多序列比对中的应用研究

免疫算法(IA)是一种新的基于生物免疫系统的寻优算法.虽然以往的免疫算法有许多优良的计算特性,但在DNA多序列比对(MSA)中已知的免疫算法模型仍有许多不足.本文对已有的免疫算法通过加入免疫算子等进行改进,在保证群体的多样性性能的同时,加入了促使群体快速持续收敛的措施,并把它应用到多序列比对中,试验结果证明了此改进算法的可行性.     

应用鼻咽癌家系资料评估HLA三座位单倍型软件推算方法的研究

目的 通过家系资料,对比分析不同统计学单倍型推算方法在HLA-A-B-C三基因座位单倍型推算运用中的准确性及有效性.方法 选择558例有完整家系资料的个体,通过SAS/Genetics、Arlequin遗传学分析软件的EM算法、ELB算法分别进行单倍体确认,计算个体单倍型频率,并与家系分析结果相比较.结果 558例研究个体中,SAS/Genetics、Arlequin遗传学分析软件的EM算法、ELB算法分别估算得到248、247和238种单倍型,推算准确率分别为88.5％、89.1％,90.3％.3种软件推算方法得到的单倍型推算准确性、最常见单倍型分布差异无统计学意义.结论 运用统计学推算软件进行群体数据的单倍型推算可获得较高的准确性,3种算法得到的常见单倍型频率差异无统计学意义.但总体来说,ELB算法更加准确.     

基于结构信息的RNA多序列比对

本研究提出了一种考虑了结构信息的同源RNA多序列比对算法,它先利用热力学方法计算出每条序列的配对概率矩阵,得到结构信息,由此构造各条序列的结构信息矢量,结合传统序列比对方法,提出优化目标函数,采用动态规划算法和渐进比对得到最后的多序列比对.试验证实了该方法的有效性.     

硫酸化胆汁酸水解酶基因BSS H1克隆、表达及活性

目的 从铜绿假单胞菌克隆出硫酸化胆汁酸水解酶(BSS)基因,并表达蛋白产物、研究其活性.方法 通过序列比对确定铜绿假单胞菌中的目的序列BSS H1;通过PCR扩增获得BSS H1基冈全序列,将其插入pET30b(+)载体,并将重组表达载体转化到大肠杆菌BL21(DE3)中诱导表达.通过优化诱导表达条件,实现重组蛋白BSS H1的高效表达;通过BSS-HSD酶联法初步研究其酶活性质.结果 工程菌扩大培养3h、以终浓度为1 mmol/L IPTG诱导5h时蛋白表达量最高;研究发现BSS H1能催化底物生成3α和3β两种构型的羟基胆汁酸,在pH 8.5时,其活性分别是(632±65) U/L和(52±4) U/L.结论 成功构建BSS H1高效表达菌株.BSS H1能催化生成两种立体异构体的特性在其他BSS中未见报道,其机制尚不明确,值得深入研究.     

无比对的生物分子序列比较方法

生物序列分析是生物信息学的主要研究领域,常常通过比较分析获取有用的信息。最常用的比较方法是序列比对,但是利用比对的序列比较假设了同源片断之间是邻接保守的,这和遗传重组相冲突,而且多序列比对在计算复杂性等方面存在困难,这些使得人们努力研究无比对的序列比较方法。本文综述了目前无比对序列比较的两类主要方法:一类基于字(低聚物)的出现率及其分布,通过出现率向量定义的笛卡尔空间中的距离计算来实现序列比较;另一类使用柯尔莫哥洛夫复杂度理论或混沌理论来实现序列比较。     

三维图像重建中基于GPU的轮廓插值加速方法

目的：针对传统的的轮廓插值算法在CPU上计算效率低的缺点,将基于距离图像的轮廓插值算法做基于GPU的并行计算加速。方法：基于形状的插值算法主要过程有：（1）轮廓平移使上下两层原始轮廓图像的形心对齐;（2）对原始轮廓图像建立一个对应的标记图像;（3）对原始轮廓图像进行距离变换,得到有不同符号标记的距离图像;（4）对距离图像进行线性插值;（5）从得到的插值距离图像中提取出插值层轮廓;（6）将插值层轮廓回移。将轮廓插值算法中的距离变换过程进行GPU并行化。使距离图像像素标识与GPU线程标识一一对应。GPU的每个线程分别计算距离图像中的一个像素：从显存中读取标记与轮廓坐标,计算出最小欧氏距离,并将有标记的距离结果保存在显存中,作为距离图像的一个像素。结果：测试表明,该方法在测验平台上加速最高达到600倍.结论：该方法加速效果明显,满足实际应用中的实时交互要求。     

常见皮肤癣菌18S～28S rDNA ITS序列同源性分析

目的分析常见皮肤癣菌内转录间隔区（ITS,包括5.8S rDNA）序列,探讨快速、准确鉴定菌种的方法;建立种系发生进化树,了解其亲缘关系.方法用形态学方法对16株皮肤癣菌做初步鉴定,PCR扩增各菌ITS区,扩增产物纯化、DNA测序,做序列比对、分析,建立系统发生树.结果检测了16株菌,包括未见文献报道的猪小孢子菌的ITS全序列,其中11株菌与形态学结果一致,1株菌鉴定为金孢子菌,4株菌通过这两种方法均不能确定.在基于ITS序列构建的N-J系统树中,将皮肤癣菌分成3组,这与依形态学所分的3属不同.结论ITS区序列分析法具有高度的准确性、敏感性,检测范围广泛、快速,可应用于菌种鉴定.但也有局限性,应与形态学鉴定相互补充.ITS区序列为今后更加合理地分类和命名皮肤癣菌提供了参考依据.     

应用噬菌体随机十二肽库筛选旋毛虫Ts87蛋白抗原表位

以抗旋毛虫Ts87蛋白单克隆抗体2A2作为靶标,对噬菌体展示随机十二肽库进行筛选.通过ELISA鉴定筛选克隆的结合特性,并对阳性克隆提取DNA进行测序分析.结果显示,经3轮生物淘洗后,目标噬菌体得到433倍富集.随机挑选20个克隆进行ELISA鉴定,其中有18个噬菌体克隆可以与单抗2A2特异性结合.测序分析发现,这18个克隆带有4种氨基酸序列,分别为:TPHPHIFYREAS、DWKAWTQMLDSY、WQIEYFrLHSLW和VSPHEYWSEL.经比对未发现这4种序列与Ts87蛋白序列有明显同源性.将这4株噬菌体克隆扩增后,经Western-blot鉴定均可被单抗2A2识别.结果表明本次筛选鉴定得到的4个噬菌体展示肽可能是旋毛虫 Ts87蛋白的模拟抗原表位.     

Prediction of missense mutation functionality depends on both the algorithm and sequence alignment employed

Multiple algorithms are used to predict the impact of missense mutations on protein structure and function using algorithm-generated sequence alignments or manually curated alignments. We compared the accuracy with native alignment of SIFT, Align-GVGD, PolyPhen-2, and Xvar when generating functionality predictions of well-characterized missense mutations (n = 267) within the BRCA1, MSH2, MLH1, and TP53 genes. We also evaluated the impact of the alignment employed on predictions from these algorithms (except Xvar) when supplied the same four alignments including alignments automatically generated by (1) SIFT, (2) Polyphen-2, (3) Uniprot, and (4) a manually curated alignment tuned for Align-GVGD. Alignments differ in sequence composition and evolutionary depth. Data-based receiver operating characteristic curves employing the native alignment for each algorithm result in area under the curve of 78-79% for all four algorithms. Predictions from the PolyPhen-2 algorithm were least dependent on the alignment employed. In contrast, Align-GVGD predicts all variants neutral when provided alignments with a large number of sequences. Of note, algorithms make different predictions of variants even when provided the same alignment and do not necessarily perform best using their own alignment. Thus, researchers should consider optimizing both the algorithm and sequence alignment employed in missense prediction.     

Uncertainty in homology inferences: assessing and improving genomic sequence alignment

Sequence alignment underpins all of comparative genomics, yet it remains an incompletely solved problem. In particular, the statistical uncertainty within inferred alignments is often disregarded, while parametric or phylogenetic inferences are considered meaningless without confidence estimates. Here, we report on a theoretical and simulation study of pairwise alignments of genomic DNA at human-mouse divergence. We find that >15% of aligned bases are incorrect in existing whole-genome alignments, and we identify three types of alignment error, each leading to systematic biases in all algorithms considered. Careful modeling of the evolutionary process improves alignment quality; however, these improvements are modest compared with the remaining alignment errors, even with exact knowledge of the evolutionary model, emphasizing the need for statistical approaches to account for uncertainty. We develop a new algorithm, Marginalized Posterior Decoding (MPD), which explicitly accounts for uncertainties, is less biased and more accurate than other algorithms we consider, and reduces the proportion of misaligned bases by a third compared with the best existing algorithm. To our knowledge, this is the first nonheuristic algorithm for DNA sequence alignment to show robust improvements over the classic Needleman-Wunsch algorithm. Despite this, considerable uncertainty remains even in the improved alignments. We conclude that a probabilistic treatment is essential, both to improve alignment quality and to quantify the remaining uncertainty. This is becoming increasingly relevant with the growing appreciation of the importance of noncoding DNA, whose study relies heavily on alignments. Alignment errors are inevitable, and should be considered when drawing conclusions from alignments. Software and alignments to assist researchers in doing this are provided at http://genserv.anat.ox.ac.uk/grape/.     

Graemlin: general and robust alignment of multiple large interaction networks

The recent proliferation of protein interaction networks has motivated research into network alignment: the cross-species comparison of conserved functional modules. Previous studies have laid the foundations for such comparisons and demonstrated their power on a select set of sparse interaction networks. Recently, however, new computational techniques have produced hundreds of predicted interaction networks with interconnection densities that push existing alignment algorithms to their limits. To find conserved functional modules in these new networks, we have developed Graemlin, the first algorithm capable of scalable multiple network alignment. Graemlin's explicit model of functional evolution allows both the generalization of existing alignment scoring schemes and the location of conserved network topologies other than protein complexes and metabolic pathways. To assess Graemlin's performance, we have developed the first quantitative benchmarks for network alignment, which allow comparisons of algorithms in terms of their ability to recapitulate the KEGG database of conserved functional modules. We find that Graemlin achieves substantial scalability gains over previous methods while improving sensitivity.     

Evaluation of methods for opto-electronic body surface sensing applied to patient position control in breast radiation therapy

The accuracy gap between the high levels of accuracy in radiotherapy planning and the uncertain set-up of each therapy fraction represents a crucial factor in the optimisation of radiation treatment. This occurs because the conventional means of patient alignment and immobilisation do not guarantee accurate implementation of the therapy plan in the actual irradiation treatment. A patient repositioning technique is proposed, based on opto-electronic motion capture and on methods of registration of body surfaces described by a limited dataset. The validation of the method was related to breast cancer radiotherapy and was based on simulated and experimental repositioning procedures involving a phantom and two subjects. With respect to previous work, the surface registration procedure was, in this case, implemented as a constrained non-linear least-square problem (constraints were given by the position of a couple of passive markers placed on the sternum), and three different algorithms were compared in terms of accuracy in misalignment detection and of computational cost. The simulation and experimental activities identified the best performing algorithm, which systematically limited the repositioning errors to below clinically acceptable thresholds (5mm), with residual surface mismatches lower than 2 mm.     

lobSTR: A short tandem repeat profiler for personal genomes

Short tandem repeats (STRs) have a wide range of applications, including medical genetics, forensics, and genetic genealogy. High-throughput sequencing (HTS) has the potential to profile hundreds of thousands of STR loci. However, mainstream bioinformatics pipelines are inadequate for the task. These pipelines treat STR mapping as gapped alignment, which results in cumbersome processing times and a biased sampling of STR alleles. Here, we present lobSTR, a novel method for profiling STRs in personal genomes. lobSTR harnesses concepts from signal processing and statistical learning to avoid gapped alignment and to address the specific noise patterns in STR calling. The speed and reliability of lobSTR exceed the performance of current mainstream algorithms for STR profiling. We validated lobSTR's accuracy by measuring its consistency in calling STRs from whole-genome sequencing of two biological replicates from the same individual, by tracing Mendelian inheritance patterns in STR alleles in whole-genome sequencing of a HapMap trio, and by comparing lobSTR results to traditional molecular techniques. Encouraged by the speed and accuracy of lobSTR, we used the algorithm to conduct a comprehensive survey of STR variations in a deeply sequenced personal genome. We traced the mutation dynamics of close to 100,000 STR loci and observed more than 50,000 STR variations in a single genome. lobSTR's implementation is an end-to-end solution. The package accepts raw sequencing reads and provides the user with the genotyping results. It is written in C/C++, includes multi-threading capabilities, and is compatible with the BAM format.     

Classification of in vivo autofluorescence spectra using support vector machines

An algorithm based on support vector machines (SVM), the most recent advance in pattern recognition, is presented for use in classifying light-induced autofluorescence collected from cancerous and normal tissues. The in vivo autofluorescence spectra used for development and evaluation of SVM diagnostic algorithms were measured from 85 nasopharyngeal carcinoma (NPC) lesions and 131 normal tissue sites from 59 subjects during routine nasal endoscopy. Leave-one-out cross-validation was used to evaluate the performance of the algorithms. An overall diagnostic accuracy of 96%, a sensitivity of 94%, and a specificity of 97% for discriminating nasopharyngeal carcinomas from normal tissues were achieved using a linear SVM algorithm. A diagnostic accuracy of 98%, a sensitivity of 95%, and a specificity of 99% for detecting NPC were achieved with a nonlinear SVM algorithm. In a comparison with previously developed algorithms using the same dataset and the principal component analysis (PCA) technique, the SVM algorithms produced better diagnostic accuracy in all instances. In addition, we investigated a method combining PCA and SVM techniques for reducing the complexity of the SVM algorithms.     

Contextual multiple sequence alignment

In a recently proposed contextual alignment model, efficient algorithms exist for global and local pairwise alignment of protein sequences. Preliminary results obtained for biological data are very promising. Our main motivation was to adopt the idea of context dependency to the multiple-alignment setting. To this aim the relaxation of the model was developed (we call this new model averaged contextual alignment) and a new family of amino acids substitution matrices are constructed. In this paper we present a contextual multiple-alignment algorithm and report the outcomes of experiments performed for the BAliBASE test set. The contextual approach turned out to give much better results for the set of sequences containing orphan genes.     

Constrained independent component analysis approach to nonobtrusive pulse rate measurements

Nonobtrusive pulse rate measurement using a webcam is considered. We demonstrate how state-of-the-art algorithms based on independent component analysis suffer from a sorting problem which hinders their performance, and propose a novel algorithm based on constrained independent component analysis to improve performance. We present how the proposed algorithm extracts a photoplethysmography signal and resolves the sorting problem. In addition, we perform a comparative study between the proposed algorithm and state-of-the-art algorithms over 45 video streams using a finger probe oxymeter for reference measurements. The proposed algorithm provides improved accuracy: the root mean square error is decreased from 20.6 and 9.5 beats per minute (bpm) for existing algorithms to 3.5 bpm for the proposed algorithm. An error of 3.5 bpm is within the inaccuracy expected from the reference measurements. This implies that the proposed algorithm provided performance of equal accuracy to the finger probe oximeter.     

A filtered backprojection algorithm for cone beam reconstruction using rotational filtering under helical source trajectory

With the evolution from multi-detector-row CT to cone beam (CB) volumetric CT, maintaining reconstruction accuracy becomes more challenging. To combat the severe artifacts caused by a large cone angle in CB volumetric CT, three-dimensional reconstruction algorithms have to be utilized. In practice, filtered backprojection (FBP) reconstruction algorithms are more desirable due to their computational structure and image generation efficiency. One of the CB-FBP reconstruction algorithms is the well-known FDK algorithm that was originally derived for a circular x-ray source trajectory by heuristically extending its two-dimensional (2-D) counterpart. Later on, a general CB-FBP reconstruction algorithm was derived for noncircular, such as helical, source trajectories. It has been recognized that a filtering operation in the projection data along the tangential direction of a helical x-ray source trajectory can significantly improve the reconstruction accuracy of helical CB volumetric CT. However, the tangential filtering encounters latitudinal data truncation, resulting in degraded noise characteristics or data manipulation inefficiency. A CB-FBP reconstruction algorithm using one-dimensional rotational filtering across detector rows (namely CB-RFBP) is proposed in this paper. Although the proposed CB-RFBP reconstruction algorithm is approximate, it approaches the reconstruction accuracy that can be achieved by exact helical CB-FBP reconstruction algorithms for moderate cone angles. Unlike most exact CB-FBP reconstruction algorithms in which the redundant data are usually discarded, the proposed CB-RFBP reconstruction algorithm make use of all available projection data, resulting in significantly improved noise characteristics and dose efficiency. Moreover, the rotational filtering across detector rows not only survives the so-called long object problem, but also avoids latitudinal data truncation existing in other helical CB-FBP reconstruction algorithm in which a tangential filtering is carried out, providing better noise characteristics, dose efficiency and data manipulation efficiency.