The alignment of biological sequences is a crucial tool in molecular biology and genome analysis. A wide variety of approaches has been proposed for multiple sequence alignment problem; however, some of them need prerequisites to help find the best alignment or some of them may suffer from the drawbacks of complexity and memory requirement so they can be only applied to cases with a limited number of sequences. In this paper, we view the multiple sequence alignment problem as an optimization problem and propose a heuristic-based genetic algorithm (GA) approach to solve it. The heuristic/GA hybrid yields better results than other well-known packages do. Experimental results are presented to illustrate the feasibility of the proposed approach.

Many techniques have been proposed for segmenting feature point trajectories tracked through a video sequence into independent motions, but objects in the scene are usually assumed to undergo general 3-D motions. As a result, the segmentation accuracy considerably deteriorates in realistic video sequences in which object motions are nearly degenerate. In this paper, we propose a multi-stage unsupervised learning scheme first assuming degenerate motions and then assuming general 3-D motions and show by simulated and real video experiments that the segmentation accuracy significantly improves without compromising the accuracy for general 3-D motions.

The availability of a low cost hardware has increased the development of distributed systems, by making then more and more accessible. In order to optimize the resources allocation on the distributed systems, some load balancing algorithms have been proposed. These algorithms distribute the application loads over the environment computers, make homogeneous the occupation of the whole environment and increase the application performance. This equal distribution prevents certain computers to get overloaded, to the detriment of the idleness of the other ones. This article proposes and analyzes the TLBAGrid, a load balancing algorithm for Grid computing environments.

Graph data in large scientific/engineering applications are often too massive to fit inside the computer's main memory. The resulting input/output (I/O) costs could be a major performance bottleneck. This paper proposes an extension to extant multilevel graph partitioning algorithms with improved I/O-efficiency. The input graph is envisioned as the union of disjoint blocks (subgraphs) of almost the same size. Each block is coarsened in turn. Recursive matching and contraction are the operations in this phase. All the coarsened blocks are then merged in an iterative manner in order to ensure that the resulting graph fits in the main memory. This graph is then treated with an in-core multilevel graph partitioning algorithm in the usual way. Our experimental results show that the larger graph size is, the more dependent on the I/O-efficiency the performance is. And our modification can easily partition very large graphs. It also exhibits considerable improvement in I/O-complexity.

An adaptive filtering algorithm based on the sliding window criterion is known to be very attractive for violent changing environments. In this paper, a new sliding window linearly constrained recursive least squares (SW-LC-RLS) algorithm based on the modified minimum mean squared error (MMSE) structure is devised for the RAKE receiver in direct sequence spread spectrum code-division multiple access (DS-SS CDMA) system over multipath fading channels, where the channel estimation scheme is accomplished at the output of adaptive filter. The proposed SW-LC-RLS algorithm has the advantage of having faster convergence property and tracking ability, and can be applied to the environments, where the narrowband interference is joined suddenly to the system, to achieve desired performance. Via computer simulation, we show that the performance, in terms of mean square errors (MSE), signal to interference plus noise ratio (SINR) and bit error rate (BER), is superior to the conventional LC-RLS and orthogonal decomposition-based LMS algorithms based on the MMSE structure.

In this paper we apply a parallel adaptive solution algorithm to simulate nanoscale double-gate metal-oxide-semiconductor field effect transistors (MOSFETs) on a personal computer (PC)-based Linux cluster with the message passing interface (MPI) libraries. Based on a posteriori error estimation, the triangular mesh generation, the adaptive finite volume method, the monotone iterative method, and the parallel domain decomposition algorithm, a set of two-dimensional quantum correction hydrodynamic (HD) equations is solved numerically on our constructed cluster system. This parallel adaptive simulation methodology with 1-irregular mesh was successfully developed and applied to deep-submicron semiconductor device simulation in our recent work. A 10 nm n-type double-gate MOSFET is simulated with the developed parallel adaptive simulator. In terms of physical quantities and refined adaptive mesh, simulation results demonstrate very good accuracy and computational efficiency. Benchmark results, such as load-balancing, speedup, and parallel efficiency are achieved and exhibit excellent parallel performance. On a 16 nodes PC-based Linux cluster, the maximum difference among CPUs is less than 6%. A 12.8 times speedup and 80% parallel efficiency are simultaneously attained with respect to different simulation cases.

By using distributed database systems, many advantages can be obtained such as database management cost, efficiency, and high integrity of systems through allocating fragments to many distributed sites with horizontal/vertical fragmentation of global database schema. To minimize costs, distributed algorithms must be applied so that database fragments are allocated to optimal sites. It is useful to replicate fragments, such as allocating many copies in many sites including load balancing. But there are too many possible combinations of each site and fragment, making it impossible to find a solution in real time, i.e., it is an NP-complete problem. This paper proposes near optimal heuristic algorithms for minimizing cost by defining a cost model based on read and update queries that are requested in many sites. Various factors are applied to the proposed algorithms for sizing efficient network resources that compute database transactions as remote query or update requests for consistency in replicated database systems. For network load balancing, incoming network traffic table is defined in each site. A request transaction from unallocated sites to allocated sites can be accessed properly at any other replicated sites by using the network traffic table. Finally, some experimental results verified the proposed algorithms by comparing actual cases of database allocation.

A new scheme for watermarking based on vector quantization (VQ) over a binary symmetric channel is proposed. By optimizing VQ indices with genetic algorithm, simulation results not only demonstrate effective transmission of watermarked image, but also reveal the robustness of the extracted watermark.

In this paper, the optimal assignment problem which assigns cells in PCS (Personal Communication Service) to switches on ATM (Asynchronous Transfer Mode) network is investigated. The cost considered in this paper has two components: one is the cost of handoff that involves two switches, and the other is the cost of cabling. This problem assumes that each cell in PCS can be assigned to two switches in ATM network. This problem is modelled as dual-homing cell assignment problem, which is a complex integral linear programming (ILP) problem. Since finding an optimal solution of this problem is NP-hard, a hybrid method which combines several heuristics and a stochastic search method (based on a simulated annealing(SA) approach) is proposed to solve this problem. The solution method consists of three phases: Primary Assignment Decision Phase (PADP), Secondary Assignment Decision Phase (SADP) and Refinement Phase (RP). The PADP and SADP are used to find good initial assignment, then domain-dependent heuristics are encoded into perturbations of SA in Refinement Phase to improve the result. Simulation results show that the proposed hybrid method is robust for this problem.

This paper proposes several novel hierarchical interconnection networks based on the (3, 3)-graphs, namely folded (3, 3)-networks, root-folded (3, 3)-networks, recursively expanded (3, 3)-networks, and flooded (3, 3)-networks. Just as the hypercubes, CCC, Peterson-based networks, and Heawood-based networks, these hierarchical networks have the following nice properties: regular topology, high scalability, and small diameters. Due to these important properties, these hierarchical networks seem to have the potential as alternatives for the future interconnection structures of multicomputer systems, especially massively parallel processors (MPPs). Furthermore, this paper will present the routing and broadcasting algorithms for these proposed networks to demonstrate that these algorithms are as elegant as the algorithms for hypercubes, CCC, and Petersen- or Heawood-based networks.

Internet traffic engineering is much important for Internet Service Providers (ISPs) today, since it can be used to fully utilize already deployed network resources. For ISPs, the requirements for traffic engineering should be simple, easy to configure, cost-effective and efficient. Based on these considerations, we propose an algorithm called Web First Adaptive Traffic Engineering (WFATE). Since World Wide Web (WWW) services dominate most of the total Internet traffic and WWW flows are not long-lived, we only apply load balancing to WWW traffic in the algorithm. It can be shown that the number of coexistent WWW flows at an ingress node is almost certainly below a bound, and thus a forward-per-flow mechanism without keeping track of the state of each flow is feasible. This mechanism can balance traffic load at fine granularity and therefore get better performance. Through simulations and performance comparison, it is shown that WFATE is quite efficient, which can improve the network throughput averagely by 26% under the "dense source" traffic pattern and 9% under the "sparse source" traffic pattern.

We analyze the Lagarias-Odlyzko low-density attack precisely, and show that this low-density attack can be applied to the Chor-Rivest and the Okamoto-Tanaka-Uchiyama cryptosystemes, which are considered to be secure against the low-density attack. According to our analysis, these schemes turn out to be no longer secure against the low-density attack.

Recently, Muramatsu proposed source coding algorithms that use the randomness of a past sequence. The technique of his source coding algorithms is one method of constructing codes from the technique of random coding. By using his technique, we propose a channel coding algorithm with random numbers which can be observed by both the encoder and the decoder where the random numbers are independent of the messages to be transmitted. Then the proposed coding algorithm can transmit messages over a discrete memoryless channel up to the channel capacity with an arbitrarily small decoding error rate and arbitrarily small bits of random numbers per message transmission asymptotically.

The goal of source localization in the brain is to estimate a set of parameters for representing source characteristics; one of such parameters is the source number. We here propose a method combining the Powell algorithm with the information criterion method for determining the optimal dipole number. The potential errors can be calculated by the Powell algorithm with the concentric 4-sphere head model and 32 electrodes, then the number of dipoles is determined by the information criterion method with the potential errors mentioned above. This method has the advantages of a high identification accuracy of dipole number and a small number of EEG data because in this method: (1) only one EEG topography is used in the computation, (2) 32 electrodes are used to obtain the EEG data, (3) the optimal dipole number can be obtained by this method. In order to prove our method to be efficient, precise and robust to noise, 10% white noise is introduced to test this method theoretically. Some investigations are presented here to show our method is an advanced approach for determining the optimal dipole number.

In this paper, we propose a new technique to generate virtual views of three-dimensional (3D) models. The technique is implemented into our facial pose transformation system, which takes only one frontal image and transforms it into virtual views. In our system, to overcome the complex of 3D geometric model, Image Based Rendering based algorithm and mesh-based methods are applied. We also introduce our new Invertible Meshwarp Algorithm, which is developed based on Two-pass Meshwarp Algorithm. Firstly, in the system, for any given person, we take a frontal face image to compose a frontal mesh for it. The standard mesh set of a specific person is created for several face sides; front, half left, half right, left and right side. The other meshes are then automatically generated based on the standard mesh set and the frontal mesh. Continually, we use Invertible Meshwarp Algorithm, which improvably solves the overlap or inversion of neighbor vertices of those created meshes. This step will finalize the generation of different views or the virtual looks of the frontal face image. We then evaluate our transformation system performance by comparing the normalized distance between several feature points in the real and transformed face images. The system is built based on C/C++ language and our result shows that the average error in the feature location is about 7% of the distance from the center of both eyes to the center of a mouth between the actual and transformed face images.

Sampling is important for many applications in research areas such as graphics, vision, and image processing. In this paper, we present a novel stratified sampling algorithm (SSA) for the coiled tubing surface with a given probability density function. The algorithm is developed from the inverse function of the integration for the areas of the coiled tubing surface. We exploit a Hierarchical Allocation Strategy (HAS) to preserve sample stratification when generating any desirable sample numbers. This permits us to reduce variances when applying our algorithm to Monte Carlo Direct Lighting for realistic image generation. We accelerate the sampling process using a segmentation technique in the integration domain. Our algorithm thus runs 324 orders of magnitude faster when using faster SSA algorithm where the order of the magnitude is proportional to the sample numbers. Finally, we employ a parabolic interpolation technique to decrease the average errors occurred for using the segmentation technique. This permits us to produce nearly constant average errors, independent of the sample numbers. The proposed algorithm is novel, efficient in computing and feasible for realistic image generation using Monte Carlo method.

The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., ε-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of ε-approximate k-wise independent permutations of small size. For any n > 0, let Sn be the set of all permutations on {0,1,..., n - 1}. In this paper, we investigate the size of families of ε-approximate k-wise independent permutations and show that (1) for any constant ε 0, if a family Sn of permutations is ε-approximate k-wise independent, then || n(n - 1) (n - k + 1) if ε< 1; || {n(n - 1) (n - k + 1)}/(1 +ε) otherwise; (2) for any constant 0< ε 1, there exists a family Sn of ε-approximate k-wise independent permutations such that || = ; (3) for any constant ε> 0 and any n = pm - 1 with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate pairwise independent permutations such that || = O(n(n - 1)/ε); (4) for any constant ε> 0 and any n = pm with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate 3-wise independent permutations such that || = O(n(n - 1)(n - 2)/ε). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.

We propose an optical packet switch (OPS) using a hybrid buffer structure for the contention resolution of asynchronous variable length packets. The hybrid buffer consists of a fiber delay line (FDL) buffer as the prime buffer and a shared electronic buffer as the supplementary buffer. For the performance evaluation, a modified void filling scheduling algorithm that can be applied to the OPS was proposed. Simulation results show that the use of the electronic buffer together with the FDL buffer significantly reduce the number of FDLs required for contention resolution and considerably lower packet loss.

The issues of comparing the similarity or dissimilarity (distance) between structures have been studied. Especially, several distances between trees and their efficient algorithms have been proposed. However, all of the tree distances are defined based on mapping between vertices only, and they are helpless to compare the tree structures whose vertices and edges hold information. In this paper, we will propose a mapping between rooted and unordered trees based on vertex translation and edge translation, and then define a distance based on proposed mapping, and develop an efficient algorithm for computing proposed distance. Proposed distance can be used to compare the similarity or distance between two natural language sentences.

In this letter, we propose a packet scheduling algorithm to support both real-time voice and video traffic for wireless multimedia data service in orthogonal frequency division multiple access (OFDMA) system. Our design objective is to maximize the number of real-time service users that can be supported in the system subject to QoS requirement of packet loss rate (PLR). Both time slots and subcarriers are taken into account as the basic resource allocation unit in OFDMA/FDD system. The simulation results show that our proposed algorithm can dramatically increase the number of users satisfying the underlying QoS requirement for the real-time service, as compared to the existing algorithm.