Abstract: The DNA fragment assembly problem is described as follows. There is a DNA sequence , over the alphabet , which is unknown. Fragments are taken from and their sequence is directly determined by sequencing machines. Each fragment corresponds to an interval contained in and the sequencing machine outputs the substring . Typically the size of interval , which is , lies in the range to , while is much larger; in some cases like, , but it may reach . Given a number of fragments we want to determine the string . Interval Graphs have been used to model this problem, but they do not account for repeats in the sequence . In this note we introduce a new formalism, Interval Graphs with Repeats, to address this issue.

Abstract: The advent of Telecom over the last years brought up many challenges for service providers. The difficulty to offer services and, in the same time, to perform their management requires an integrated solution for both, service provisioning and management. In this paper, we outline an infrastructure for performing such tasks. This infrastructure allows to create Virtual Active Networks (VANs) and install services in Telecom environments based on the Active Networking technology. Besides service provisioning, the framework performs some management functions taking into account mobile services. The management system is based on a mobile agent platform and considers the management of VANs, where services can migrate from a VAN to another. We focus on three specific management areas: accounting, performance monitoring and configuration. We tested our system in the management of two Internet-based Telecom services, Call Forwarding and Virtual Private Network.

Abstract: The watershed transform and the morphological reconstruction are two of the most important operators for image segmentation in the framework of mathematical morphology. In many situations, the segmentation requires the classical watershed transform of a reconstructed image. In this paper, we introduce the IFT-watershed from gray scale marker - a method to compute at the same time, the reconstruction and the classical watershed transform of the reconstructed image, without explicit computation of any regional minima. The method is based on the Image Foresting Transform (IFT) - a unified and efficient approach to reduce image processing tasks to a minimum-cost path forest problem in a graph. As additional contributions, we demonstrate why other reconstruction algorithms are not watersheds, and present a family of simple, yet efficient IFT-based watershed algorithms: classical, watershed from labeled marker, from binary marker with on-the-fly labeling, and from gray scale marker with on-the-fly labeling and bounded cost.

Abstract: In Medical Imaging, shell rendering (SR) and shear-warp rendering (SWR) are two ultra-fast and effective methods for volume visualization. We have previously shown the fact that, typically, SWR can be on the average 1.38 times faster than SR, but it requires from 2 to 8 times more memory space than SR. In this paper, we propose an extension of the compact shell data structure utilized in SR to allow shear-warp factorization of the viewing matrix in order to obtain speed up gains for SR, without paying the high storage price of SWR. The new approach is called shear-warp shell rendering (SWSR). The paper describes the methods, points out their major differences in the computational aspects, and presents a comparative analysis of them in terms of speed, storage, and image quality. The experiments involve hard and fuzzy boundaries of 10 different objects of various sizes, shapes, and topologies, rendered on a 1GHz Pentium-III PC with 512MB RAM, utilizing surface and volume rendering strategies. The results indicate that SWSR offers the best speed and storage characteristics compromise among these methods. We also show that SWSR improves the rendition quality over SR, and provides renditions similar to those produced by SWR.

Abstract: We consider the -dimensional cube packing problem ( d-CPP): given a list of -dimensional cubes and (an unlimited quantity of) -dimensional unit-capacity cubes, called bins, find a packing of into the minimum number of bins. We present two approximation algorithms for d-CPP, for fixed . The first algorithm has an asymptotic performance bound that can be made arbitrarily close to . The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to . To our knowledge, these results improve the bounds known so far for and , and are the first results with bounds that are not exponential in the dimension.

Abstract: In this paper, a procedure for resource allocation method in switchlet networks is introduced. The procedure is based on restricting the search space for the solution of a multicommodity flow problem The proposed approach is accurate, and amenable to real time implementation.

Resumo: A Bacia de Campos é uma área no mar onde a Petrobrás explora petróleo. Nesta área existe uma série de locais que são considerados como promissores poços de petróleo. Antes que o petróleo possa ser extraído, estes poços potenciais precisam ser desenvolvidos. O objetivo é produzir um escalonamento das atividades necessárias ao desenvolvimento dos poços, de forma a maximizar a produção de petróleo num determinado período de tempo, e sujeito à uma série de restrições, tais como restrições de precedência tecnológica entre as atividades, especificidade dos recursos e sua adequação às várias atividades, roteamento de barcos e sondas, entre outras. É proposta uma abordagem híbrida para a resolução desse problema. A abordagem combina técnicas de programação por restrições (CP) e meta-heurísticas do tipo tabu. Em cada vizinho, um problema de sequenciamento é solucionado e um primeiro teste de factibilidade é realizado sem a utilização da programação por restrições. Em seguida, o tempo de início de cada atividade é estabelecido pela programação por restrições. Nas instâncias testadas neste trabalho, são consideradas até 500 atividades e 130 poços de petróleo produtores em potencial. Modelos de programação linear inteira foram usados para provar que as soluções obtidas utilizando a técnica híbrida proposta estão a menos de 9% de um limitante superior global. Finalmente, para estabelecer quão robusta era a técnica proposta, foi realizada uma análise de sensibilidade sobre as instâncias consideradas, indicando que a técnica é capaz de produzir bons resultados em instâncias similares.

Abstract: Bacia de Campos is a large area in the sea where Petrobras explores petroleum in deep waters. There are a lot of specific locations in this site that have been determined as promising oil wells. Before the extraction begins, these locations must be fully developed. The objective is to construct a schedule maximize the oil production in a given amount of time, subject to a number of restrictions such as a given precedence relation among teh activities, the proper match between resources and activities, and resource routing, among others . We propose a hybrid approach that combines constraint programming (CP) techniques and abu search in order to solve the problem. At each neighbor, a scheduling problem and a first feasibility test are performed initially, without using CP. Next, CP is used to assign the start time of the activities. Up to 500 activities and 130 oil wells are considered in the instances tested. We used integer linear models to prove that the solutions obtained are less than 9% from an global upper bound. Finally, to estabilish the robuteness of our approach, a sensibility analysis was performed indicating that the technique performs well when solving similar instances.

Abstract: The need to reduce the huge demand for bandwidth of video-on-demand services has led to the consideration of techniques based on multicast for the deployment of such services on a large scale. Interactiveness, a desirable feature of video services, includes the capacity to per form VCR operations. Whenever a viewer issues a VCR operation, his/her video stream be comes unsynchronized with that of his/her multicast group. The present paper introduces a novel approach for determining the number of video channels needed to support such interac tiveness. Moreover, it investigates the performance of interactive systems with a reserved pool of channels for the support of VCR operations. Systems with batching and with both batching and piggybacking are analysed.

Abstract: In this technical note we introduce a set of cuts for 0-1 Integer Programming with a strong geometrical flavor. These are the spherical and cylindrical inequalities. We show that the geometrical cuts are in one-to-one correspondence with the canonical cuts introduced by Balas and Jeroslow. Moreover, we show how the well-known subtour elimination constraints for the Traveling Salesman Problem can be obtained via geometrical cuts. By presenting the subtour elimination constraints in this way, we give another easy and intuitive way to explain the validity of such inequalities. We show that the arguments used to derive the subtour elimination constraint as geometrical cut can be repeated to derive strong valid inequalities that are known for other combinatorial optimization problems.

Abstract: Efficient address register allocation has been shown to be a central problem in code generation for processors with restricted addressing modes. This paper extends previous work on Global Array Reference Allocation (GARA), the problem of allocating address registers to array references in loops. It describes two heuristics to the problem, presenting experimental data to support them. In addition, it proposes an approach to solve GARA optimally which, albeit computationally exponential, is useful to measure the efficiency of other methods. Experimental results, using the MediaBench benchmark, reveal that the proposed heuristics can solve the majority of the benchmark loops near optimality in polynomial-time. A substantial execution time speedup is reported for the benchmark programs, after compiled with the original and the optimized versions of GCC.

Abstract: A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph is extremal if the number of perfect matchings of is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of . We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using some of our previously published results[*] we find all the extremal cubic matching covered graphs.

[*] On a Conjecture of Lovász Concerning Bricks: I. The Characteristic of a Matching Covered Graph. II. Bricks of Finite Characteristic. To appear in J. of Combinatorial Theory, Series B; published electronically on Feb/2002.

Resumo: Proteínas de transporte são elementos importantes em todos os tipos de organismos. Em células humanas, doenças como fibrose cística e algumas formas de diabete são causadas por mutações em transportadores.

Uma comissão de especialistas em transportadores tem estudado estas proteínas há algum tempo e se encarregou em categorizá-las em famílias, dando-lhes um ``TC number'' (TC = Transport Commission). Assim, todo transportador deve ter um número TC.

Nos últimos anos foram disponibilizadas, no site do grupo de estudo do prof. Milton Saier, da University of California - San Diego (UCSD), páginas que descrevem com detalhes estas famílias de transportadores e citam diversos exemplos de proteínas de transporte para cada família. Por serem muito informativas e possuírem milhares de proteínas-exemplo, o que permite automação e tratamento bioinformático, estas páginas foram uma das motivações do nosso projeto.

O nosso objetivo é desenvolver programas especialistas em reconhecer e classificar proteínas e sistemas de transporte, baseados na classificação TC.

Este documento apresenta a descrição de uma primeira versão das ferramentas, acompanhada de resultados preliminares e os planos para passos futuros.

Abstract: Transport proteins are important elements in all kinds of organisms. In human cells, diseases like cystic fibrosis and some forms of diabetes are due to mutations on transporters.

A commission of specialists categorized these proteins into families giving them a ``TC number'' (TC = Transport Commission). Every transporter must have a TC number.

In recent years, detailed pages describing these transporter families were made available by Professor Milton Saier's research group in a web site at the University of California - San Diego (UCSD), where they list many examples of transport proteins for each family. Because they are fairly informative and have thousands of protein examples, these pages were one of the motivations for the current project.

The project aim is to develop expert systems for recognizing and classifying transport proteins based on the TC classification.

This document presents the first version of our classification tools, preliminaries results, and plans for future work.

Resumo: Neste relatório técnico, heurísticas baseadas em algoritmos evolutivos (algoritmos genéticos) e técnicas de busca local (busca tabu) são aplicadas ao problema das escalas de serviço para as enfermarias do Hospital das Clínicas da Unicamp. Também é descrita uma ferramenta computacional para construir as escalas de serviço do hospital. Essa ferramenta compreende módulos resolvedores que implementam versões dessas heurísticas e também uma interface amigável para estimular o uso da ferramenta pelos administradores do hospital.

Resumo: Recentemente foi mostrado que dados dois genomas multi-cromossomais é fácil calcular a série de peso mínimo de fusões, fissões e transposições necessárias para transformar um genoma no outro, quando é associado um peso duas vezes maior as transposições do que as fusões e fissões. Neste trabalho trabalho apresentaremos vários resultados sobre o problema da distância de fusão, fissão e transposição quando associamos pesos arbitrários às transposições. Algumas variações do problema também serão aqui estudadas. Por exemplo, apresentaremos um algoritmo polinomial para o problema da distância sintênica quando apenas os eventos de fusão e fissão são admissíveis.

Abstract: Recently we have shown that given two multi-chromossomal genomes it is easy to compute the minimum weight series of fusions, fissions, and transpositions needed to transform one genome into the other, when the weight associated to transpositions is twice as large as that associated to fusions and fissions. In this work we present several results on the computation of distance when an arbitrary weight is associated to transpositions. Some variations of the problem are also studied. For instance we present a polynomial time algorithm for the problem of syntenic distance when only the events of fusions and fissions are admitted.