http://hdl.handle.net/10230/5542 2013-05-18T17:28:11Z 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/20518 Mutual information of IID complex Gaussian signals on block Rayleigh-faded channels Rusek, Fredrik; Lozano Solsona, Àngel; Jindal, Nihar We present a method to compute, quickly and efficiently, the mutual information achieved by an IID (independent identically distributed) complex Gaussian signal on a block Rayleigh-faded channel without side information at the receiver. The method accommodates both scalar and MIMO (multiple-input multiple-output) settings. Operationally, this mutual information represents the highest spectral efficiency that can be attained using Gaussian codebooks. Examples are provided that illustrate the loss in spectral efficiency caused by fast fading and how that loss is amplified when multiple transmit antennas are used. These examples are further enriched by comparisons with the channel capacity under perfect channel-state information at the receiver, and with the spectral efficiency attained by pilot-based transmission. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20517 Outage probability analysis for MRC in η-μ fading channels with co-channel interference Morales-Jiménez, David; Paris, José F.; Lozano Solsona, Àngel Exact closed-form expressions are obtained for the outage probability of maximal ratio combining in η-μ fading channels with antenna correlation and co-channel interference. The scenario considered in this work assumes the joint presence of background white Gaussian noise and independent Rayleigh-faded interferers with arbitrary powers. Outage probability results are obtained through an appropriate generalization of the moment-generating function of the η-μ fading distribution, for which new closed-form expressions are provided. 2012-01-01T00:00:00Z http://hdl.handle.net/10230/20510 Multiple target tracking using random sets Angelosante, Daniele; Biglieri, Ezio; Lops, Marco This paper presents several algorithms for joint estimation of the target number and state in a time-varying scenario. Building on the results presented in [1], which considers estimation of the target number only, we assume that not only the target number, but also their state evolution must be estimated. In this context, we extend to this new scenario the Rao-Blackwellization procedure of [1] to compute Bayes recursions, thus defining reduced-complexity solutions for the multi-target set estimator. A performance assessment is finally given both in terms of Circular Position Error Probability - aimed at evaluating the accuracy of the estimated track - and in terms of Cardinality Error Probability, aimed at evaluating the reliability of the target number estimates. 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/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/20507 Fading models and metrics for contemporary wireless systems Jindal, Nihar; Lozano Solsona, Àngel The purpose of this paper is to examine (1) some of the models commonly used to represent fading, and (2) the information-theoretic metrics most commonly used to evaluate performance over those models. We raise the question of whether these models and metrics remain adequate in light of the advances that wireless systems have undergone over the last two decades. Weaknesses are pointed out, and ideas on possible fixes are put forth. Comunicació presentada en la 44th Asilomar Conference on Signals, Systems and Computers, celebrada els dies 7, 8, 9 i 10 de novembre de 2010 a Pacific Grove, Califòrnia (EUA), organitzada per la Naval Postgraduate School (Monterey, CA) i l’ATK Mission Research (Monterey, CA). 2010-01-01T00:00:00Z http://hdl.handle.net/10230/20506 On iterative performance of LDPC and Root-LDPC codes over block-fading channels Andriyanova, Iryna; Biglieri, Ezio; Boutros, Joseph Jean This paper presents our investigation on iterative decoding performances of some sparse-graph codes on block-fading Rayleigh channels. The considered code ensembles are standard LDPC codes and Root-LDPC codes, first proposed in and shown to be able to attain the full transmission diversity. We study the iterative threshold performance of those codes as a function of fading gains of the transmission channel and propose a numerical approximation of the iterative threshold versus fading gains, both both LDPC and Root-LDPC codes. Also, we show analytically that, in the case of 2 fading blocks, the iterative threshold root of Root-LDPC codes is proportional to (α1 α2)1, where α1 and α2 are corresponding fading gains. From this result, the full diversity property of Root-LDPC codes immediately follows. Comunicació presentada en la 48th Annual Allerton Conference on Communications, Control and Computing, celebrada els dies 29 i 30 de setembre i 1 d’octubre de 2010 a Monticello, Illinois (EUA), organitzada pel Coordinated Science Laboratory de l’University of Illinois at Urbana-Champaign. 2010-01-01T00:00:00Z http://hdl.handle.net/10230/20505 Optimum pilot overhead in wireless communication: a unified treatment of continuous and block-fading channels Lozano Solsona, Àngel; Jindal, Nihar The optimization of the pilot overhead in wireless fading channels is investigated, and the dependence of this overhead on various system parameters of interest (e.g., fading rate, signal-to-noise ratio) is quantified. The achievable pilot-based spectral efficiency is expanded with respect to the fading rate about the no-fading point, which leads to an accurate order expansion for the pilot overhead. This expansion identifies that the pilot overhead, as well as the spectral efficiency penalty with respect to a reference system with genie-aided CSI (channel state information) at the receiver, depend on the square root of the normalized Doppler frequency. It is also shown that the widely-used block fading model is a special case of more accurate continuous fading models in terms of the achievable pilot-based spectral efficiency. Furthermore, it is established that the overhead optimization for multiantenna systems is effectively the same as for single-antenna systems with the normalized Doppler frequency multiplied by the number of transmit antennas. Comunicació presentada en la 16th European Wireless Conference 2010 (EW '10), celebrada els dies 12, 13, 14 i 15 d’abril de 2010 a Lucca (Itàlia), organitzada per l’IMT Institute for Advanced Studies. 2010-01-01T00:00:00Z http://hdl.handle.net/10230/20504 Outage thresholds of LDPC codes over nonergodic block-fading channels Andriyanova, Iryna; Biglieri, Ezio; Boutros, Joseph Jean This paper derives approximations allowing the estimation of outage probability for standard irregular LDPC codes and full-diversity Root-LDPC codes used over nonergodic block-fading channels. Two separate approaches are discussed: a numerical approximation, obtained by curve fitting, for both code ensembles, and an analytical approximation for Root-LDPC codes, obtained under the assumption that the slope of the iterative threshold curve of a given code ensemble matches the slope of the outage capacity curve in the high-SNR regime. Comunicació presentada en la 16th European Wireless Conference 2010 (EW '10), celebrada els dies 12, 13, 14 i 15 d’abril de 2010 a Lucca (Itàlia), organitzada per l’IMT Institute for Advanced Studies. 2010-01-01T00:00:00Z http://hdl.handle.net/10230/20503 A systolic array for linear MIMO detection based on an all-swap lattice reduction algorithm Wang, Ni-Chun; Biglieri, Ezio; Yao, Kung A systolic array to implement lattice-reduction-aided linear detection is proposed for a MIMO receiver. The lattice reduction algorithm and the ensuing linear detections are operated in the same array, which can be hardware-efficient. All-swap lattice reduction algorithm (ASLR) is considered for the systolic design. ASLR is a variant of the LLL algorithm, which processes all lattice basis vectors within one iteration. Lattice-reduction-aided linear detection based on ASLR and LLL algorithms have very similar bit-error-rate performance, while ASLR is more time efficient in the systolic array, especially for systems with a large number of antennas. Comunicació presentada en la 34th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '09), celebrada els dies 19, 20, 21, 22, 23 i 24 d’abril de 2009 a Taipei, (Taiwan), organitzada per l’Institute of Electrical and Electronics Engineers (IEEE). 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20502 De-hyping transmit diversity in modern MIMO cellular systems Jindal, Nihar; Lozano Solsona, Àngel A contemporary perspective on the tradeoff between transmit antenna diversity and spatial multi-plexing is provided. It is argued that, in the context of modern cellular systems and for the operating points of interest, transmission techniques that utilize all available spatial degrees of freedom for multiplexing outperform techniques that explicitly sacrifice spatial multiplexing for diversity. Reaching this conclusion, however, requires that the channel and some key system features be adequately modeled; failure to do so may bring about starkly different conclusions. As a specific example, this contrast is illustrated using the 3GPP Long-Term Evolution system design. Comunicació presentada en la Global Telecommunications Conference (GLOBECOM '09), celebrada els dies 30 de novembre, 1, 2, 3 i 4 de desembre de 2009 a Honolulu, Hawaii (EUA), organitzada per l’Institute of Electrical and Electronics Engineers (IEEE). 2009-01-01T00:00:00Z http://hdl.handle.net/10230/20501 ClubADSL: When your neighbors are your friends Giustiniano, Domenico; Gomà Llairo, Eduard; Morillo Pozo, Julián; López Toledo, Alberto; Rodríguez, Pablo ADSL is becoming the standard form of residential and small-business broadband Internet access due to, primarily, its low deployment cost. These ADSL residential lines are often deployed with 802.11 Access Points (AP) that provide wireless connectivity. Given the density of ADSL deployment, it is often possible for a residential wireless client to be in range of several other APs, belonging to neighbors, with ADSL connectivity. While the ADSL technology has showed evident limits in terms of capacity (with speeds ranging 1-10 Mbps), the short-range wireless communication can guarantee a much higher capacity (up to 20 Mbps). Furthermore, the ADSL links in the neighborhood are generally under-utilized, since ADSL subscribers do not connect 100% of the time. Therefore, it is possible for a wireless client to simultaneously connect to several APs in range and effectively aggregate their available ADSL bandwidth. In this paper, we introduce ClubADSL, a wireless client that can simultaneously connect to several APs in range on different frequencies and aggregate both their downlink and uplink capacity. ClubADSL is a software that runs locally on the client-side, and it requires neither modification to the existing Internet infrastructure, nor any hardware/protocol upgrades to the 802.11 local area network. We show the feasibility of ClubADSL in seamlessly transmitting TCP traffic, and validate its implementation both in controlled scenarios and with current applications over real ADSL lines. In particular we show that a ClubADSL client can greatly benefit from the aggregated download bandwidth in the case of server-client applications such as video streaming, but can also take advantage of the increased upload bandwidth greatly reducing download times with incentive-based P2P applications such as BitTorrent. Comunicació presentada en el Symposium on Computers and Communications (ISCC '09), celebrat els dies 5, 6, 7 i 8 de juliol de 2009 a Sussa (Tunísia), organitzat per l’Institute of Electrical and Electronics Engineers (IEEE). 2009-01-01T00:00:00Z