http://hdl.handle.net/10230/8581 2013-05-20T15:15:46Z http://hdl.handle.net/10230/20578 Width and serialization of classical planning problems Geffner, Hector; Lipovetzky, Nir We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20563 Sequencing primate genomes: what have we learned? Marquès i Bonet, Tomàs, 1975-; Ryder, Oliver A.; Eichler, Evan E. We summarize the progress in whole-genome sequencing and analyses of primate genomes. These emerging genome datasets have broadened our understanding of primate genome evolution revealing unexpected and complex patterns of evolutionary change. This includes the characterization of genome structural variation, episodic changes in the repeat landscape, differences in gene expression, new models regarding speciation, and the ephemeral nature of the recombination landscape. The functional characterization of genomic differences important in primate speciation and adaptation remains a significant challenge. Limited access to biological materials, the lack of detailed phenotypic data and the endangered status of many critical primate species have significantly attenuated research into the genetic basis of primate evolution. Next-generation sequencing technologies promise to greatly expand the number of available primate genome sequences; however, such draft genome sequences will likely miss critical genetic differences within complex genomic regions unless dedicated efforts are put forward to understand the full spectrum of genetic variation. 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20558 A burst of segmental duplications in the genome of the African great ape ancestor Marquès i Bonet, Tomàs, 1975-; Kidd, Jeffrey M.; Ventura, Mario; Graves, Tina A.; Cheng, Ze; Hillier, LaDeana W.; Jiang, Zhaoshi; Baker, Carl; Malfavon-Borja, Ray; Fulton, Lucinda A.; Alkan, Can; Aksay, Gozde; Girirajan, Santhosh; Siswara, Priscillia; Chen, Lin; Cardone, Maria Francesca; Navarro i Cuartiellas, Arcadi, 1969-; Mardis, Elaine R.; Wilson, Richard K.; Eichler, Evan E. It is generally accepted that the extent of phenotypic change between human and great apes is dissonant with the rate of molecular change. Between these two groups, proteins are virtually identical, cytogenetically there are few rearrangements that distinguish ape-human chromosomes, and rates of single-base-pair change and retrotransposon activity have slowed particularly within hominid lineages when compared to rodents or monkeys. Studies of gene family evolution indicate that gene loss and gain are enriched within the primate lineage. Here, we perform a systematic analysis of duplication content of four primate genomes (macaque, orang-utan, chimpanzee and human) in an effort to understand the pattern and rates of genomic duplication during hominid evolution. We find that the ancestral branch leading to human and African great apes shows the most significant increase in duplication activity both in terms of base pairs and in terms of events. This duplication acceleration within the ancestral species is significant when compared to lineage-specific rate estimates even after accounting for copy-number polymorphism and homoplasy. We discover striking examples of recurrent and independent gene-containing duplications within the gorilla and chimpanzee that are absent in the human lineage. Our results suggest that the evolutionary properties of copy-number mutation differ significantly from other forms of genetic mutation and, in contrast to the hominid slowdown of single-base-pair mutations, there has been a genomic burst of duplication activity at this period during human evolution. 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20557 The origins and impact of primate segmental duplications Marquès i Bonet, Tomàs, 1975-; Girirajan, Santosh; Eichler, Evan E. Duplicated sequences are substrates for the emergence of new genes and are an important source of genetic instability associated with rare and common diseases. Analyses of primate genomes have shown an increase in the proportion of interspersed segmental duplications (SDs) within the genomes of humans and great apes. This contrasts with other mammalian genomes that seem to have their recently duplicated sequences organized in a tandem configuration. In this review, we focus on the mechanistic origin and impact of this difference with respect to evolution, genetic diversity and primate phenotype. Although many genomes will be sequenced in the future, resolution of this aspect of genomic architecture still requires high quality sequences and detailed analyses. 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20555 Asymptotic capacity of static multiuser channels with an unknown number of users Biglieri, Ezio We examine a multiple-access communication system in which multiuser detection is performed without knowledge of the number of active interferers. Using a statistical-physics approach, we compute the single-user channel capacity and spectral efficiency in the large-system limit. Comunicació presentada al 11th International Symposium on Wireless Personal Multimedia Communications (WPMC '08), celebrat els dies 8, 9, 10 i 11 de setembre de 2008 a Lapland, Finlàndia, i organitzat pel Centre for Wireless Communications i el National Institute of Information and Communications Technology. 2008-01-01T00:00:00Z http://hdl.handle.net/10230/20531 Sequencing human-gibbon breakpoints of synteny reveals mosaic new insertions at rearrangement sites Girirajan, Santosh; Chen, Lin; Graves, Tina; Marquès i Bonet, Tomàs, 1975-; Ventura, Mario; Fronick, Catrina; Fulton, Lucinda; Rocchi, Mariano; Fulton, Robert S.; Wilson, Richard K.; Mardis, Elaine R.; Eichler, Evan E. The gibbon genome exhibits extensive karyotypic diversity with an increased rate of chromosomal rearrangements during evolution. In an effort to understand the mechanistic origin and implications of these rearrangement events, we sequenced 24 synteny breakpoint regions in the white-cheeked gibbon (Nomascus leucogenys, NLE) in the form of high-quality BAC insert sequences (4.2 Mbp). While there is a significant deficit of breakpoints in genes, we identified seven human gene structures involved in signaling pathways (DEPDC4, GNG10), phospholipid metabolism (ENPP5, PLSCR2), beta-oxidation (ECH1), cellular structure and transport (HEATR4), and transcription (ZNF461), that have been disrupted in the NLE gibbon lineage. Notably, only three of these genes show the expected evolutionary signatures of pseudogenization. Sequence analysis of the breakpoints suggested both nonclassical nonhomologous end-joining (NHEJ) and replication-based mechanisms of rearrangement. A substantial number (11/24) of human-NLE gibbon breakpoints showed new insertions of gibbon-specific repeats and mosaic structures formed from disparate sequences including segmental duplications, LINE, SINE, and LTR elements. Analysis of these sites provides a model for a replication-dependent repair mechanism for double-strand breaks (DSBs) at rearrangement sites and insights into the structure and formation of primate segmental duplications at sites of genomic rearrangements during evolution. 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20530 Death and resurrection of the human IRGM gene Bekpen, Cemalettin; Marquès i Bonet, Tomàs, 1975-; Alkan, Can; Antonacci, Francesca; Leogrande, Maria Bruna; Ventura, Mario; Kidd, Jeffrey M.; Siswara, Priscillia; Howard, Jonathan C.; Eichler, Evan E. Immunity-related GTPases (IRG) play an important role in defense against intracellular pathogens. One member of this gene family in humans, IRGM, has been recently implicated as a risk factor for Crohn's disease. We analyzed the detailed structure of this gene family among primates and showed that most of the IRG gene cluster was deleted early in primate evolution, after the divergence of the anthropoids from prosimians ( about 50 million years ago). Comparative sequence analysis of New World and Old World monkey species shows that the single-copy IRGM gene became pseudogenized as a result of an Alu retrotransposition event in the anthropoid common ancestor that disrupted the open reading frame (ORF). We find that the ORF was reestablished as a part of a polymorphic stop codon in the common ancestor of humans and great apes. Expression analysis suggests that this change occurred in conjunction with the insertion of an endogenous retrovirus, which altered the transcription initiation, splicing, and expression profile of IRGM. These data argue that the gene became pseudogenized and was then resurrected through a series of complex structural events and suggest remarkable functional plasticity where alleles experience diverse evolutionary pressures over time. Such dynamism in structure and evolution may be critical for a gene family locked in an arms race with an ever-changing repertoire of intracellular parasites. 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20529 Gorilla genome structural variation reveals evolutionary parallelisms with chimpanzee Ventura, Mario; Catacchio, Claudia R.; Alkan, Can; Marquès i Bonet, Tomàs, 1975-; Saijadian, Saba; Graves, Tina A.; Hormozdiari, Fereydoun; Navarro i Cuartiellas, Arcadi, 1969-; Malig, Maika; Baker, Carl; Lee, Choli; Turner, Emily H.; Chen, Lin; Kidd, Jeffrey M.; Archidiacono, Nicoletta; Shendure, Jay; Wilson, Richard K.; Eichler, Evan E. Structural variation has played an important role in the evolutionary restructuring of human and great ape genomes. Recent analyses have suggested that the genomes of chimpanzee and human have been particularly enriched for this form of genetic variation. Here, we set out to assess the extent of structural variation in the gorilla lineage by generating 10-fold genomic sequence coverage from a western lowland gorilla and integrating these data into a physical and cytogenetic framework of structural variation. We discovered and validated over 7665 structural changes within the gorilla lineage, including sequence resolution of inversions, deletions, duplications, and mobile element insertions. A comparison with human and other ape genomes shows that the gorilla genome has been subjected to the highest rate of segmental duplication. We show that both the gorilla and chimpanzee genomes have experienced independent yet convergent patterns of structural mutation that have not occurred in humans, including the formation of subtelomeric heterochromatic caps, the hyperexpansion of segmental duplications, and bursts of retroviral integrations. Our analysis suggests that the chimpanzee and gorilla genomes are structurally more derived than either orangutan or human genomes. 2011-01-01T00:00:00Z http://hdl.handle.net/10230/20509 Multiuser detection with an unknown number of active users: receiver design Angelosante, Daniele; Biglieri, Ezio; Lops, Marco In multiuser detection, the set of users active at any time may be unknown to the receiver. In these conditions, optimum reception consists of detecting simultaneously the set of active users and their data, problem that can be solved exactly by applying random-set theory (RST) and Bayesian recursions (BR). However, implementation of optimum receivers may be limited by their complexity, which grows exponentially with the number of potential users. In this paper we examine three strategies leading to reduced-complexity receivers. In particular, we show how a simple approximation of BRs enables the use of Sphere Detection (SD) algorithm, which exhibits satisfactory performance with limited complexity. Comunicació presentada en la 16th European Signal Processing Conference (EUSIPCO 2008), celebrada els dies 25, 26, 27, 28 i 29 d’agost de 2008 a Lausana (Suïssa), organitzada per la European Association for Signal Processing (EURASIP). 2008-01-01T00:00:00Z http://hdl.handle.net/10230/20508 Silver space-time trellis-coded modulation Biglieri, Ezio; Hong, Yi; Viterbo, Emanuele Silver Code (SilC) was originally discovered in [1–4] for 2×2 multiple-input multiple-output (MIMO) transmission. It has non-vanishing minimum determinant 1/7, slightly lower than Golden code, but is fast-decodable, i.e., it allows reduced-complexity maximum likelihood decoding [5–7]. In this paper, we present a multidimensional trellis-coded modulation scheme for MIMO systems [11] based on set partitioning of the Silver Code, named Silver Space-Time Trellis Coded Modulation (SST-TCM). This lattice set partitioning is designed specifically to increase the minimum determinant. The branches of the outer trellis code are labeled with these partitions. Viterbi algorithm is applied for trellis decoding, while the branch metrics are computed by using a sphere-decoding algorithm. It is shown that the proposed SST-TCM performs very closely to the Golden Space-Time Trellis Coded Modulation (GST-TCM) scheme, yet with a much reduced decoding complexity thanks to its fast-decoding property. Comunicació presentada en la 16th European Signal Processing Conference (EUSIPCO 2008), celebrada els dies 25, 26, 27, 28 i 29 d’agost de 2008 a Lausana (Suïssa), organitzada per la European Association for Signal Processing (EURASIP). 2008-01-01T00:00:00Z http://hdl.handle.net/10230/20495 Opportunities for a cultural specific approach in the computational description of music Serra, Xavier The current research in Music Information Retrieval (MIR) is showing the potential that the Information Technologies can have in music related applications. A major research challenge in that direction is how to automatically describe/annotate audio recordings and how to use the resulting descriptions to discover and appreciate music in new ways. But music is a complex phenomenon and the description of an audio recording has to deal with this complexity. For example, each music culture has specificities and emphasizes different musical and communication aspects, thus the musical recordings of each culture should be described differently. At the same time these cultural specificities give us the opportunity to pay attention to musical concepts and facets that, despite being present in most world musics, are not easily noticed by listeners. In this paper we present some of the work done in the CompMusic project, including ideas and specific examples on how to take advantage of the cultural specificities of different musical repertoires. We will use examples from the art music traditions of India, Turkey and China. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20494 Carnatic music: Svara, Gamaka, Motif and Raga identity Krishna, T. M.; Ishwar, Vignesh Over the last century in Karnatik music, the method of understanding raga has been to break it down into its various components, svara, scale, gamaka, and phrases. In this paper, an attempt is made to define the abstract concept of raga in its entirety within the aesthetics of Karnatik music considering the various components and their symbiotic relationship. This paper also attempts to prove that the identity of a raga exists as a whole. Section 2 explains the concept of a fundamental musical note or svara. Section 3 illustrates the concept of gamaka or inflections. Section 4 delves into the concept of raga in detail and then flows into Section 5 which enunciates the identity of a raga in terms of svara, gamaka, and phraseology. The paper concludes in Section 6, and Section 7 gives the references. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20493 A Musically aware system for browsing and interacting with audio music collections Sordo, Mohamed; Koduri, Gopala Krishna; Sentürk, Sertan; Gulati, Sankalp; Serra, Xavier In the context of the CompMusic project we are developing methods to automatically describe/annotate audio music recordings pertaining to various music cultures. As a way to demonstrate the usefulness of the methods we are also developing a system to browse and interact with specific audio collections. The system is an online web application that interfaces with all the data gathered (audio, scores plus contextual information) and all the descriptions that are automatically generated with the developed methods. In this paper we present the basic architecture of the proposed system, the types of data sources that it includes, and we mention some of the culture specific issues that we are working on for its development. The system is in a preliminary stage but it shows the potential that MIR technologies can have in browsing and interacting with music collections of various cultures. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20492 Incorporating features of distribution and progression for automatic Makam classification Ünal, Erdem; Bozkurt, Baris; Karaosmanoğlu, M. Kemal Automatic classification of makams from symbolic data is a rarely studied topic. In this paper, first a review of an n-gram based approach is presented using various representations of the symbolic data. While a high degree of precision can be obtained, confusion happens mainly for makams using (almost) the same scale and pitch hierarchy but differ in overall melodic progression, seyir. To further improve the system, first n-gram based classification is tested for various sections of the piece to take into account a feature of the seyir that melodic progression starts in a certain region of the scale. In a second test, a hierarchical classification structure is designed which uses n-grams and seyir features in different levels to further improve the system. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20491 Analysis of the folksonomy of freesound Font, Frederic; Serra, Xavier User generated content shared in online communities is often described using collaborative tagging systems where users assign labels to content resources. As a result, a folksonomy emerges that relates a number of tags with the resources they label and the users that have used them. In this paper we analyze the folksonomy of Freesound, an online audio clip sharing site which contains more than two million users and 150,000 user-contributed sound samples covering a wide variety of sounds. By following methodologies taken from similar studies, we compute some metrics that characterize the folksonomy both at the global level and at the tag level. In this manner, we are able to better understand the behavior of the folksonomy as a whole, and also obtain some indicators that can be used as metadata for describing tags themselves. We expect that such a methodology for characterizing folksonomies can be useful to support processes such as tag recommendation or automatic annotation of online resources. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20490 A method for extracting semantic information from on-line art music discussion forums Sordo, Mohamed; Serrà Julià, Joan; Koduri, Gopala Krishna; Serra, Xavier In this paper a method for extracting semantic information from online music discussion forums is proposed. The semantic relations are inferred from the co-occurrence of musical concepts in forum posts, using network analysis. The method starts by defining a dictionary of common music terms in an art music tradition. Then, it creates a complex network representation of the online forum by matching such dictionary against the forum posts. Once the complex network is built we can study different network measures, including node relevance, node co-occurrence and term relations via semantically connecting words. Moreover, we can detect communities of concepts inside the forum posts. The rationale is that some music terms are more related to each other than to other terms. All in all, this methodology allows us to obtain meaningful and relevant information from forum discussions. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20489 Applause identification and its relevance to archival of Carnatic music Sarala, Padi; Ishwar, Vignesh; Bellur, Ashwin; Murthy, Hema A. A Carnatic music concert is made up of a sequence of pieces, where each piece corresponds to a particular genre and ra¯aga (melody). Unlike a western music concert, the artist may be applauded intra-performance inter-performance. Most Carnatic music that is archived today correspond to a single audio recordings of entire concerts. The purpose of this paper is to segment single audio recordings into a sequence of pieces using the characteristic features of applause and music. Spectral flux, spectral entropy change quite significantly from music to applause and vice-versa. The characteristics of these features for a subset of concerts was studied. A threshold based approach was used to segment the pieces into music fragments and applauses. Preliminary results on recordings 19 concerts from matched microphones show that the EER is about 17% for a resolution of 0.25 seconds. Further, a parameter called CUSUM is estimated for the applause regions. The CUSUM values determine the strength of the applause. The CUSUM is used to characterise the highlights of a concert. Comunicació presentada al 2nd CompMusic Workshop, celebrat els dies 12 i 13 de juliol de 2012 a Istanbul (Turquia), organitzat per CompMusic. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20478 Large-system analysis of a CDMA dynamic channel under a Markovian input process Biglieri, Ezio; Grossi, Emanuele; Lops, Marco; Tauste Campo, Adrià We study the minimum mean square error (MMSE) and the multiuser efficiency η of large dynamic multiple access communication systems in which optimal multiuser detection is performed at the receiver as the number and the identities of active users is allowed to change at each transmission time. The system dynamics are ruled by a Markov model describing the evolution of the channel occupancy and a large-system analysis is performed when the number of observations grow large. Starting on the equivalent scalar channel and the fixed-point equation tying multiuser efficiency and MMSE, we extend it to the case of a dynamic channel, and derive lower and upper bounds for the MMSE (and, thus, for η as well) holding true in the limit of large signal–to–noise ratios and increasingly large observation time T. Comunicació presentada al IEEE International Symposium on Information Theory (ISIT '08), celebrat a Toronto (Ontario, Canadà) els dies 6, 7, 8, 9, 10 i 11 de juliol de 2008, organitzat per l'Institute of Electrical and Electronics Engineers (IEEE). 2008-01-01T00:00:00Z http://hdl.handle.net/10230/20477 Sequential estimation of time-varying multipath channel for MIMO-OFDM systems Angelosante, Daniele; Biglieri, Ezio; Lops, Marco In this paper, we introduce a pilot-aided multipath channel estimator for Multiple-Input Multiple-Output (MIMO) Orthogonal Frequency Division Multiplexing (OFDM) systems. Typical estimation algorithms assume the number of multipath components and delays to be known and constant, while their amplitudes may vary in time. In this work, we focus on the more realistic assumption that also the number of channel taps is unknown and time-varying. The estimation problem arising from this assumption is solved using Random Set Theory (RST), which is a probability theory of finite sets. Due to the lack of a closed form of the optimal filter, a Rao-Blackwellized Particle Filter (RBPF) implementation of the channel estimator is derived. Simulation results demonstrate the estimator effectiveness. Comunicació presentada al IEEE International Symposium on Information Theory (ISIT '08), celebrat a Toronto (Ontario, Canadà) els dies 6, 7, 8, 9, 10 i 11 de juliol de 2008, organitzat per l'Institute of Electrical and Electronics Engineers (IEEE). 2008-01-01T00:00:00Z http://hdl.handle.net/10230/20473 Pathway databases and tools for their exploitation: benefits, current limitations and challenges Bauer-Mehren, Anna; Furlong, Laura I.; Sanz, Ferran In past years, comprehensive representations of cell signalling pathways have been developed by manual curation from literature, which requires huge effort and would benefit from information stored in databases and from automatic retrieval and integration methods. Once a reconstruction of the network of interactions is achieved, analysis of its structural features and its dynamic behaviour can take place. Mathematical modelling techniques are used to simulate the complex behaviour of cell signalling networks, which ultimately sheds light on the mechanisms leading to complex diseases or helps in the identification of drug targets. A variety of databases containing information on cell signalling pathways have been developed in conjunction with methodologies to access and analyse the data. In principle, the scenario is prepared to make the most of this information for the analysis of the dynamics of signalling pathways. However, are the knowledge repositories of signalling pathways ready to realize the systems biology promise? In this article we aim to initiate this discussion and to provide some insights on this issue. 2009-01-01T00:00:00Z