Multiple sequence alignment （MSA） is the alignment among more than two molecular biological sequences, which is a fundamental method to analyze evolutionary events such as mutations, insertions, deletions, and re-ar...Multiple sequence alignment （MSA） is the alignment among more than two molecular biological sequences, which is a fundamental method to analyze evolutionary events such as mutations, insertions, deletions, and re-arrangements. In theory, a dynamic programming algorithm can be employed to produce the optimal MSA. However, this leads to an explosive increase in computing time and memory consumption as the number of sequences increases （Taylor, 1990）. So far, MSA is still regarded as one of the most challenging problems in bioinformatics and computational biology （Chatzou et al., 2016）.展开更多
A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multipl...A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.展开更多
To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computat...To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computation, a fast algorithm is proposed. The proposed algorithm includes three techniques. First, a linear array A[N] is introduced to store the sum of every row of the distance matrix （the same as SK）, which can eliminate many repeated computations. Secondly, the value of A [i] is computed only once at the beginning of the algorithm, and is updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of operational taxonomic units （OTUs） i and j is designed, and the correctness of the formula is proved. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases, constructing a tree with 2 000 OTUs in 3 min on a current desktop computer. To earn the time with the cost of the space and reduce the computations in the innermost loop are the basic solutions for algorithms with many loops.展开更多
A fast interactive segmentation algorithm of image-sequences based on relative fuzzy connectedness is presented. In comparison with the original algorithm, the proposed one, with the same accuracy, accelerates the seg...A fast interactive segmentation algorithm of image-sequences based on relative fuzzy connectedness is presented. In comparison with the original algorithm, the proposed one, with the same accuracy, accelerates the segmentation speed by three times for single image. Meanwhile, this fast segmentation algorithm is extended from single object to multiple objects and from single-image to image-sequences. Thus the segmentation of multiple objects from complex hackground and batch segmentation of image-sequences can be achieved. In addition, a post-processing scheme is incorporated in this algorithm, which extracts smooth edge with one-pixel-width for each segmented object. The experimental results illustrate that the proposed algorithm can obtain the object regions of interest from medical image or image-sequences as well as man-made images quickly and reliably with only a little interaction.展开更多
In this paper,a time-frequency associated multiple signal classification(MUSIC)al-gorithm which is suitable for through-wall detection is proposed.The technology of detecting hu-man targets by through-wall radar can b...In this paper,a time-frequency associated multiple signal classification(MUSIC)al-gorithm which is suitable for through-wall detection is proposed.The technology of detecting hu-man targets by through-wall radar can be used to monitor the status and the location information of human targets behind the wall.However,the detection is out of order when classical MUSIC al-gorithm is applied to estimate the direction of arrival.In order to solve the problem,a time-fre-quency associated MUSIC algorithm suitable for through-wall detection and based on S-band stepped frequency continuous wave(SFCW)radar is researched.By associating inverse fast Fouri-er transform(IFFT)algorithm with MUSIC algorithm,the power enhancement of the target sig-nal is completed according to the distance calculation results in the time domain.Then convert the signal to the frequency domain for direction of arrival(DOA)estimation.The simulations of two-dimensional human target detection in free space and the processing of measured data are com-pleted.By comparing the processing results of the two algorithms on the measured data,accuracy of DOA estimation of proposed algorithm is more than 75%,which is 50%higher than classical MUSIC algorithm.It is verified that the distance and angle of human target can be effectively de-tected via proposed algorithm.展开更多
由于MUSIC(MUltiple SIgnal Classification)算法需要大量的乘法运算和三角函数求值,导致其实时处理能力较弱。为此,该文首先对均匀线阵和均匀圆阵的阵列结构进行分析,提取导向矢量的一些性质。然后,利用Hermite矩阵的性质对复数乘法进...由于MUSIC(MUltiple SIgnal Classification)算法需要大量的乘法运算和三角函数求值,导致其实时处理能力较弱。为此,该文首先对均匀线阵和均匀圆阵的阵列结构进行分析,提取导向矢量的一些性质。然后,利用Hermite矩阵的性质对复数乘法进行分解,再组建两个实值向量以减少乘法运算次数。最后,利用导向矢量的性质提出一种基于查表的新算法。新算法既没有三角函数求值运算,又不需要大量的存储空间。仿真实验结果表明新算法在没有改变MUSIC算法谱估计的效果的前提下,将MUSIC算法的运算速率提高了50倍以上。因此,新算法具有广阔的应用前景。展开更多
基金supported by the National Key R&D Program of China (Nos. 2017YFB0202600, 2016YFC1302500, 2016YFB0200400 and 2017YFB0202104)the National Natural Science Foundation of China (Nos. 61772543, U1435222, 61625202, 61272056 and 61771331)Guangdong Provincial Department of Science and Technology (No. 2016B090918122)
文摘Multiple sequence alignment （MSA） is the alignment among more than two molecular biological sequences, which is a fundamental method to analyze evolutionary events such as mutations, insertions, deletions, and re-arrangements. In theory, a dynamic programming algorithm can be employed to produce the optimal MSA. However, this leads to an explosive increase in computing time and memory consumption as the number of sequences increases （Taylor, 1990）. So far, MSA is still regarded as one of the most challenging problems in bioinformatics and computational biology （Chatzou et al., 2016）.
文摘A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.
文摘To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computation, a fast algorithm is proposed. The proposed algorithm includes three techniques. First, a linear array A[N] is introduced to store the sum of every row of the distance matrix （the same as SK）, which can eliminate many repeated computations. Secondly, the value of A [i] is computed only once at the beginning of the algorithm, and is updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of operational taxonomic units （OTUs） i and j is designed, and the correctness of the formula is proved. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases, constructing a tree with 2 000 OTUs in 3 min on a current desktop computer. To earn the time with the cost of the space and reduce the computations in the innermost loop are the basic solutions for algorithms with many loops.
文摘A fast interactive segmentation algorithm of image-sequences based on relative fuzzy connectedness is presented. In comparison with the original algorithm, the proposed one, with the same accuracy, accelerates the segmentation speed by three times for single image. Meanwhile, this fast segmentation algorithm is extended from single object to multiple objects and from single-image to image-sequences. Thus the segmentation of multiple objects from complex hackground and batch segmentation of image-sequences can be achieved. In addition, a post-processing scheme is incorporated in this algorithm, which extracts smooth edge with one-pixel-width for each segmented object. The experimental results illustrate that the proposed algorithm can obtain the object regions of interest from medical image or image-sequences as well as man-made images quickly and reliably with only a little interaction.
文摘In this paper,a time-frequency associated multiple signal classification(MUSIC)al-gorithm which is suitable for through-wall detection is proposed.The technology of detecting hu-man targets by through-wall radar can be used to monitor the status and the location information of human targets behind the wall.However,the detection is out of order when classical MUSIC al-gorithm is applied to estimate the direction of arrival.In order to solve the problem,a time-fre-quency associated MUSIC algorithm suitable for through-wall detection and based on S-band stepped frequency continuous wave(SFCW)radar is researched.By associating inverse fast Fouri-er transform(IFFT)algorithm with MUSIC algorithm,the power enhancement of the target sig-nal is completed according to the distance calculation results in the time domain.Then convert the signal to the frequency domain for direction of arrival(DOA)estimation.The simulations of two-dimensional human target detection in free space and the processing of measured data are com-pleted.By comparing the processing results of the two algorithms on the measured data,accuracy of DOA estimation of proposed algorithm is more than 75%,which is 50%higher than classical MUSIC algorithm.It is verified that the distance and angle of human target can be effectively de-tected via proposed algorithm.
文摘由于MUSIC(MUltiple SIgnal Classification)算法需要大量的乘法运算和三角函数求值,导致其实时处理能力较弱。为此,该文首先对均匀线阵和均匀圆阵的阵列结构进行分析,提取导向矢量的一些性质。然后,利用Hermite矩阵的性质对复数乘法进行分解,再组建两个实值向量以减少乘法运算次数。最后,利用导向矢量的性质提出一种基于查表的新算法。新算法既没有三角函数求值运算,又不需要大量的存储空间。仿真实验结果表明新算法在没有改变MUSIC算法谱估计的效果的前提下,将MUSIC算法的运算速率提高了50倍以上。因此,新算法具有广阔的应用前景。
