Search

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação é na área de Biologia Computacional e se propõe a estudar a montagem de fragmentos de DNA pelo método Ordered Shotgun Sequencing (088). A montagem de fragmentos de DNA é uma das etapas de um projeto de seqüenciamento total do genoma de um organismo. Com o crescimento do tamanho dos genomas a serem seqüenciados e do aumento da complexidade dos organismos estudados, os problemas para se montar um DNA, como trechos repetidos no genoma, também aumentaram. Até os anos noventa, o método mais popular de montagem de fragmentos era o 8hotgun, que quebra a molécula de DNA em fragmentos de mais ou menos 500 pares de bases que serão desvendados em laboratórios de seqüenciamento. Conhecendo-se os fragmentos, é a vez de se descobrir como eles se encaixam, através de sobreposições, e ordená-los. No final, espera-se que os algoritmos nos retomem a seqüência do DNA. Em 1993, dois biólogos propuseram a montagem de fragmentos 088, que quebra a molécula de DNA em intervalos bem maiores, resultando em fragmentos que chamaremos de clones, e seqüencia apenas as suas pontas, deixando a parte central desconhecida. Agora, além da seqüência dos fragmentos, teremos a informação de ligação e distância entre as pontas do clone. Com essas informações e das sobreposições entre as pontas" tenta-se encontrar as posições relativas dos clones no DNA. Um bloco ordenado de fragmentos de DNA por causa das sobreposições e das ligações de clone, será denominado scaffold. As suas partes desconhecidas serão desvendadas em outras iterações, que é uma característica da montagem de fragmentos de DNA 08S. Em 1998, ano que nossos estudos começaram, não haviam trabalhos computacionais que tirassem proveito dessa técnica, até que em 2000 surgiram trabalhos relatando projetos genoma que utilizaram a montagem OS8 com sucesso. Em nosso trabalho, propusemos dois algoritmos para encontrar scaffolds e um ambiente de simulação para executar as iterações feitas pelo método 088 e montar genomas artificialmente gerados. Foram feitos vários testes para medir o desempenho dos algoritmos propostos em termos de tempo total de processamento em CPU, e número de iterações e de clones seqüenciados para terminar a montagem 088. Por último, identificamos várias questões importantes sobre os algoritmos que merecem um estudo mais aprofundado. Abstract: This is a dissertation in the area of Computational Biology. We propose to study the DNA fragment assembly problem using the Ordered Shotgun Sequencing (OSS) method. The DNA fragment assembly problem is one step of a complete genome sequencing project. With the growing size of the sequenced genomes and the increasing complexity of the studied organisms, problems such as repeated regions increased as well. The OSS method is an attempt to mitigate those problems. Until the nineties, the most popular method of DNA fragment assembly was Shotgun, which breaks the DN A inolecule into pieces of about 500 base pairs that are revealed by sequencing laboratories. Given the fragments, it is necessary to find out what their relative position is in the original DNA molecule by using overlap information to order them. In the end, the algorithms are supposed to give us the DNA sequence. In 1993 two biologists proposed the OSS method for fragment assembly, which breaks the DNA into quite bigger pieces, resulting in fragments called clones in this dissertation. Just the ends of the clones are sequenced, leaving the central part unknown. Besides the fragment sequences, we know how far one end is from the other, and their relative orientation. Based on this information and on the overlaps between done ends, a~ ordered block of DNA fragments called scaffold can be formed. The unknown part will be revealed by subsequent iterations, an intrinsic characteristic of OSS DNA fragment assembly. Our studies began in 1998 when there was no computational work exploring the OSS technique. The first papers reporting on the successful use of OSS assembly in genome projects appeared in 2000 In this work, we propose two scaffold-finding algorithms and present a simulation environment built to test them. The environment generates artificial data, promotes the iterations, and keeps track of the amount of sequencing, number of iterations, and processing time for the algorithm being tested. Finally, we identified many important questions about the algorithms which deserve further studies. Mestrado Mestre em Ciência da Computação

Orientador: Ricardo da Silva Torres Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Informação geográfica é usualmente encontrada em objetos digitais (como documentos, imagens e vídeos), sendo de grande interesse utilizá-la na implementação de diferentes serviços. Por exemplo, serviços de navegação baseados em mapas e buscas geográficas podem se beneficiar das localizações geográficas associadas a objetos digitais. A implementação destes serviços, no entanto, demanda o uso de coleções de dados geocodificados. Este trabalho estuda a combinação de conteúdo textual e visual para geocodificar objetos digitais e propõe um arcabouço de agregação de listas para geocodificação multimodal. A informação textual e visual de vídeos e imagens é usada para definir listas ordenadas. Em seguida, elas são combinadas e a nova lista ordenada resultante é usada para definir a localização geográfica de vídeos e imagens. Uma arquitetura que implementa essa proposta foi projetada de modo que módulos específicos para cada modalidade (e.g., textual ou visual) possam ser aperfeiçoados independentemente. Outro componente é o módulo de fusão responsável pela combinação das listas ordenadas definidas por cada modalidade. Outra contribuição deste trabalho é a proposta de uma nova medida de avaliação da efetividade de métodos de geocodificação chamada Weighted Average Score (WAS). Ela é baseada em ponderações de distâncias que permitem avaliar a efetividade de uma abordagem, considerando todos os resultados de geocodificação das amostras de teste. O arcabouço proposto foi validado em dois contextos: desafio Placing Task da iniciativa MediaEval 2012, que consiste em atribuir, automaticamente, coordenadas geográficas a vídeos; e geocodificação de fotos de prédios da Virginia Tech (VT) nos EUA. No contexto do desafio Placing Task, os resultados mostram como nossa abordagem melhora a geocodificação em comparação a métodos que apenas contam com uma modalidade (sejam descritores textuais ou visuais). Nós mostramos ainda que a proposta multimodal produziu resultados comparáveis às melhores submissões que também não usavam informações adicionais além daquelas disponibilizadas na base de treinamento. Em relação à geocodificação das fotos de prédios da VT, os experimentos demostraram que alguns dos descritores visuais locais produziram resultados efetivos. A seleção desses descritores e sua combinação melhoraram esses resultados quando a base de conhecimento tinha as mesmas características da base de teste Abstract: Geographical information is often enclosed in digital objects (like documents, images, and videos) and its use to support the implementation of different services is of great interest. For example, the implementation of map-based browser services and geographic searches may take advantage of geographic locations associated with digital objects. The implementation of such services, however, demands the use of geocoded data collections. This work investigates the combination of textual and visual content to geocode digital objects and proposes a rank aggregation framework for multimodal geocoding. Textual and visual information associated with videos and images are used to define ranked lists. These lists are later combined, and the new resulting ranked list is used to define appropriate locations. An architecture that implements the proposed framework is designed in such a way that specific modules for each modality (e.g., textual and visual) can be developed and evolved independently. Another component is a data fusion module responsible for combining seamlessly the ranked lists defined for each modality. Another contribution of this work is related to the proposal of a new effectiveness evaluation measure named Weighted Average Score (WAS). The proposed measure is based on distance scores that are combined to assess how effective a designed/tested approach is, considering its overall geocoding results for a given test dataset. We validate the proposed framework in two contexts: the MediaEval 2012 Placing Task, whose objective is to automatically assign geographical coordinates to videos; and the task of geocoding photos of buildings from Virginia Tech (VT), USA. In the context of Placing Task, obtained results show how our multimodal approach improves the geocoding results when compared to methods that rely on a single modality (either textual or visual descriptors). We also show that the proposed multimodal approach yields comparable results to the best submissions to the Placing Task in 2012 using no additional information besides the available development/training data. In the context of the task of geocoding VT building photos, performed experiments demonstrate that some of the evaluated local descriptors yield effective results. The descriptor selection criteria and their combination improved the results when the used knowledge base has the same characteristics of the test set Doutorado Ciência da Computação Doutora em Ciência da Computação

Energy and storage restrictions are relevant variables that software applications should be concerned about when running in low-power environments. In particular, computer vision (CV) applications exemplify well that concern, since conventional uniform image sensors typically capture large amounts of data to be further handled by the appropriate CV algorithms. Moreover, much of the acquired data are often redundant and outside of the application’s interest, which leads to unnecessary processing and energy spending. In the literature, techniques for sensing and re-sampling images in non-uniform fashions have emerged to cope with these problems. In this study, we propose Application-Oriented Retinal Image Models that define a space-variant configuration of uniform images and contemplate requirements of energy consumption and storage footprints for CV applications. We hypothesize that our models might decrease energy consumption in CV tasks. Moreover, we show how to create the models and validate their use in a face detection/recognition application, evidencing the compromise between storage, energy, and accuracy. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited

Students, fisheries professionals, and the general public may value computer-facilitated assistance for fish identification and access to ecological and life history information. We developed SuperIDR, a software package supporting such applications, by utilizing the search and data retrieval capabilities of digital libraries, as well as key features of tablet PCs. We demonstrated SuperIDR utilizing a database with information on 207 freshwater fishes of Virginia. A user may annotate fish images and identify fishes by using a dichotomous key; searching for key words, similar images, subimages, or annotations on images; or combinations of these approaches. Students using the software demonstrated enhanced ability to correctly identify specimens. Their comments led to improvements, including the addition of new features. The PC-based system for identifying freshwater fishes of Virginia may be downloaded and modified. SuperIDR is a prototype for PC-based species identification applications—the syste...

Social media (i.e., Twitter, Facebook, Flickr, YouTube) and other services with user-generated content have made a staggering amount of information (and misinformation) available. Government officials seek to leverage these resources to improve services and communication with citizens. Yet, the sheer volume of social data streams generates substantial noise that must be filtered. Nonetheless, potential exists to identify issues in real time, such that emergency management can monitor and respond to issues concerning public safety. By detecting meaningful patterns and trends in the stream of messages and information flow, events can be identified as spikes in activity, while meaning can be deciphered through changes in content. This paper presents findings from a pilot study we conducted between June and December 2010 with government officials in Arlington, Virginia (and the greater National Capitol Region around Washington, DC) with a view to understanding the use of social media by government officials as well as community organizations, businesses and the public. We are especially interested in understanding social media use in crisis situations (whether severe or fairly common, such as traffic or weather crises).

Many scholarly tasks involve working with subdocuments, or contextualized fine-grain information, i.e., with information that is part of some larger unit. A digital library (DL) facil- itates management, access, retrieval, and use of collections of data and metadata through services. However, most DLs do not provide infrastructure or services to support working with subdocuments. Superimposed information (SI) refers to new information that is created to reference subdocu- ments in existing information resources. We combine this idea of SI with traditional DL services, to define and develop a DL with SI (SI-DL). We explored the use of subimages and evaluated the use of a prototype SI-DL (SuperIDR) in fish species identification, a scholarly task that involves work- ing with subimages. The contexts and strategies of working with subimages in SuperIDR suggest new and enhanced sup- port (SI-DL services) for scholarly tasks that involve working with subimages, including new ways of querying and search- ing for subimages and associated information. The main contribution of our work are the insights gained from these findings of use of subimages and of SuperIDR (a prototype SI-DL), which lead to recommendations for the design of digital libraries with superimposed information.

The Sugarcane EST project (SUCEST) produced 291,904 expressed sequence tags (ESTs) in a consortium that involved 74 sequencing and data mining laboratories. We created a web site for this project that served as a ‘meeting point’ for receiving, processing, analyzing, and providing services to help explore the sequence data. In this paper we describe the information pathway that we implemented to support this project and a brief explanation of the clustering procedure, which resulted in 43,141 clusters.O projeto SUCEST (Sugarcane EST Project) produziu 291.904 ESTs de cana-de-açúcar. Nesse projeto, o Laboratório de Bioinformática criou o web site que foi o "ponto de encontro" dos 74 laboratórios de sequenciamento e data mining que fizeram parte do consórcio para o projeto. O Laboratório de Bioinformática (LBI) recebeu, processou, analisou e disponibilizou ferramentas para a exploração dos dados. Neste artigo os dados, serviços e programas implementados pelo LBI para o projeto são descritos, incluindo o procedimento de clustering que gerou 43.141 clusters.

Orientadores: Eduardo Alves do Valle Junior, Lin Tzy Li Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: De todos os cânceres de pele, melanoma representa apenas 1% dos casos, mas 75% das mortes. O prognóstico do melanoma é bom quando detectado cedo, mas deteriora rápido ao longo que a doença progride. Ferramentas automatizadas podem prover triagem mais rápida, ajudando médicos a focar em pacientes ou lesões de risco. As características da doença --- raridade, letalidade, rápida progressão, e diagnóstico sutil --- fazem a triagem de melanoma automática particularmente desafiadora. O objetivo deste trabalho é melhor compreender como Deep Learning pode ser utilizado --- mais precisamente, Redes Neurais Convolucionais --- para classificar corretamente imagens de lesões de pele. Para isso, este trabalho está dividido em duas linhas de pesquisa. Primeiro, o estudo está focado na transferibilidade de características das redes CNN pré-treinadas. O objetivo principal desse tópico é estudar como as características transferidas se comportam em diferentes esquemas, com o objetivo de gerar melhores características para a camada de decisão. Em um segundo tópico, esse estudo incidirá na melhoria das métricas de classificação, que é o objetivo geral. Sobre a transferibilidade das características, foram realizados experimentos para analisar a forma como os diferentes esquemas de transferência afetariam a Área sob a Curva ROC (AUC): treinar uma CNN a partir do zero; transferir o conhecimento de uma CNN pré-treinada com imagens gerais ou específicas; realizar uma transferência dupla, que é uma sequência de treinamento onde em um primeiro momento a rede é treinada com imagens gerais, em um segundo momento com as imagens específicas, e, finalmente, em um terceiro momento com as imagens de melanoma. A partir desses experimentos, aprendemos que a transferência de aprendizagem é uma boa prática, assim como é o ajuste fino. Os resultados também sugerem que modelos mais profundos conduzem a melhores resultados. Hipotetizamos que a transferência de aprendizagem de uma tarefa relacionada sob ponto de vista médico (no caso, a partir de um dataset de imagens de retinopatia) levaria a melhores resultados, especialmente no esquema de transferência dupla, mas os resultados mostraram o oposto, sugerindo que a adaptação de tarefas muito específicas representa desafios específicos. Sobre a melhoria das métricas, discute-se o pipeline vencedor utilizado no International Skin Imaging Collaboration (ISIC) Challenge 2017, alcançando o estado da arte na classificação de melanoma com 87.4% AUC. A solução é baseada em stacking/meta learning dos modelos Inception v4 e Resnet101, realizando fine tuning enquanto executa a aumentação de dados nos conjuntos de treino e teste. Também comparamos diferentes técnicas de segmentação --- multiplicação elemento a elemento da imagem da lesão de pele e sua máscara de segmentação, e utilizar a máscara de segmentação como quarto canal --- com uma rede treinada sem segmentação. A rede sem segmentação é a que obteve melhor desemepnho (96.0% AUC) contra a máscara de segmentação como quarto canal (94.5% AUC). Nós também disponibilizamos uma implementação de referência reprodutível com todo o código desenvolvido para as contribuições desta dissertação Abstract: From all skin cancers, melanoma represents just 1% of cases, but 75% of deaths. Melanoma¿s prognosis is good when detected early, but deteriorates fast as the disease progresses. Automated tools may play an essential role in providing timely screening, helping doctors focus on patients or lesions at risk. However, due to the disease¿s characteristics --- rarity, lethality, fast progression, and diagnosis subtlety --- automated screening for melanoma is particularly challenging. The objective of this work is to understand better how can we use Deep Learning --- more precisely, Convolutional Neural Networks --- to correctly classify images of skin lesions. This work is divided into two lines of investigation to achieve the objective. First, the study is focused on the transferability of features from pretrained CNN networks. The primary objective of that thread is to study how the transferred features behave in different schemas, aiming at generating better features to the classifier layer. Second, this study will also improve the classification metrics, which is the overall objective of this line of research. On the transferability of features, we performed experiments to analyze how different transfer schemas would impact the overall Area Under the ROC Curve (AUC) training a CNN from scratch; transferring from pretrained CNN on general and specific image databases; performing a double transfer, in a sequence from general to specific and finally melanoma databases. From those experiments, we learned that transfer learning is a good practice, as is fine tuning. The results also suggest that deeper models lead to better results. We expected that transfer learning from a related task (in the case, from a retinopathy image database) would lead to better outcomes, but results showed the opposite, suggesting that adaptation from particular tasks poses specific challenges. On the improvement of metrics, we discussed the winner pipeline used in the International Skin Imaging Collaboration (ISIC) Challenge 2017, reaching state-of-the-art results on melanoma classification with 87.4% AUC. The solution is based on the stacking/meta-learning from Inception v4 and Resnet101 models, fine tuning them while performing data augmentation on the train and test sets. Also, we compare different segmentation techniques - elementwise multiplication of the skin lesion image and its mask, and input the segmentation mask as a fourth channel - with a network trained without segmentation. The network with no segmentation is the one who performs better (96.0% AUC) against segmentation mask as a fourth channel (94.5% AUC). We made available a reproducible reference implementation with all developed source code for the contributions of this thesis Mestrado Engenharia de Computação Mestre em Engenharia Elétrica CNPQ 133530/2016-7 CAPES FAPESP

Orientador: Anderson de Rezende Rocha Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: No mundo conectado atual, Recuperação de Informação (IR) tem se tornado um campo de pesquisa de crescente interesse, sendo um problema presente em muitas aplicações modernas. Dentre os muitos desafios no desenvolvimento the sistemas de IR está uma correta avaliação de performance desses sistemas. Avaliação \emph{offline}, entretanto, se limita na maioria dos casos ao \emph{benchamark} e comparação de performance entre diferentes sistemas. Esse fato levou ao surgimento do problema denomidado Predição de Performance de Consulta (QPP), cujo objetivo é estimar, em tempo de consulta, a qualidade dos resultados obtidos. Nos últimos anos, QPP recebeu grande atenção na literatura, sobretudo no contexto de busca textual. Ainda assim, QPP também tem suas limitações, principalmente por ser uma maneira indireta de estimar a performance de sistemas de IR. Nessa tese, investigamos formular o problema de QPP como um problema de \emph{predição de relevância}: a tarefa de predizer, para um determinado $\topk$, quais resultados de uma consulta são de fato relevantes para ela, de acordo com uma referência de relevância existente. Apesar de notavelmente desafiador, predição de relevância é não só uma maneira mais natural de estimar performance, como também com diversas aplicações. Nessa tese, apresentamos três famílias de métodos de predição de relevância: estatísticos, aprendizado, e rotulação sequencial. Todos os métodos nessas famílias tiveram sua efetividade avaliada em diversos experimentos em recuperação de imagens por conteúdo, cobrindo uma vasta gama de conjuntos de dados de grande-escala, assim como diferentes configurações de recuperação. Mostramos que é possível gerar predições de relevância precisas, para grandes valores de $k$, não só connhecendo pouco do sistema de IR analisado, como também de forma eficiente o bastante para ser aplicável em tempo de consulta. Finalizamos esta tese discutindo alguns caminhos possíveis para melhorar os resultados obtidos, assim como trabalhos futuros nesse campo de pesquisa Abstract: In today¿s connected world, Information Retrieval (IR) has become one of the most ubiquitous problems, being part of many modern applications. Among all challenges in designing IR systems, how to evaluate their performance is ever-present. Offline evaluation, however, is mostly limited to benchmarking and comparison of different systems, which has pushed a growing interest in predicting, at query time, the performance of an IR system. Query Performance Prediction (QPP) is the name given to the problem of estimating the quality of results retrieved by an IR system in response to a query. In the past few years, this problem received much attention, especially by the text retrieval community. Yet, QPP is still limited as only an indirect way of estimating the performance of IR systems. In this thesis, we investigate formulating the QPP problem as a \emph{relevance prediction} one: the task of predicting, for a specific $\topk$, which results of a query are relevant to it, according to some existing relevance reference. Though remarkably challenging, relevance prediction is not only a more natural way of predicting performance but also one with significantly more applications. In this thesis, we present three families of relevance prediction approaches: statistical, learning, and sequence labeling. All methods within those families are evaluated concerning their effectiveness in several content-based image retrieval experiments, covering several large-scale datasets and retrieval settings. The experiments in this thesis show that it is feasible to perform relevance prediction for $k$ values as large as 30, with minimal information about the underlying IR system, and efficiently enough to be performed at query time. This thesis is concluded by offering some potential paths for improving the current results, as well as future research in this particular field Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES CNPQ 168326/2017-5