LANCIA GIUSEPPE

Prof. LANCIA GIUSEPPE

Università degli Studi di Udine
orcid

Research Focus & Metrics

Academic Career Length

32Years (1995-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2002 in Briefings in Bioinformatics
Verified
Journal Article
Open access
PDF file
RLRoss Lippert
Ross Lippert
RSRussell Schwartz
Russell Schwartz
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
SISorin Istrail
Sorin Istrail
With the consensus human genome sequenced and many other sequencing projects at varying stages of completion, greater attention is being paid to the genetic differences among individuals and abilities of those differences to predict phenotypes. A significant obstacle to such work is the difficulty and expense of determining haplotypes - sets of various genetically linked because of their proximity on the genome - for large numbers of individuals for use in association studies. This paper presents some algorithmic considerations in a new approach for haplotype determination: inferring haplotypes from localised polymorphism data gathered from short genome 'fragments'. Formalised models of the biological system under consideration are examined, given a variety of assumptions about the goal of the problem and the charater of optimal solutions. Some theoretical results and algorithms for handling haplotype assembly given models are then sketched. The primary conclusion is that some important simplified variants of the problem yield tractable problems while more general variants tend to be intractable in the worst case.

17 August 2001
Verified
Book Chapter
Closed access
PDF file
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
VBVineet Bafna
Vineet Bafna
SISorin Istrail
Sorin Istrail
RLRoss Lippert
Ross Lippert
RSRussell Schwartz
Russell Schwartz

1 January 2004 in Journal of Computational Biology
Verified
Journal Article
Closed access
ACAlberto Caprara
Alberto Caprara
RCRobert Carr
Robert Carr
SISorin Istrail
Sorin Istrail
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
BWBrian Walenz
Brian Walenz
Protein structure comparison is a fundamental problem for structural genomics, with applications to drug design, fold prediction, protein clustering, and evolutionary studies. Despite its importance, there are very few rigorous methods and widely accepted similarity measures known for this problem. In this paper we describe the last few years of developments on the study of an emerging measure, the contact map overlap (CMO), for protein structure comparison. A contact map is a list of pairs of residues which lie in three-dimensional proximity in the protein's native fold. Although this measure is in principle computationally hard to optimize, we show how it can in fact be computed with great accuracy for related proteins by integer linear programming techniques. These methods have the advantage of providing certificates of near-optimality by means of upper bounds to the optimal alignment value. We also illustrate effective heuristics, such as local search and genetic algorithms. We were able to obtain for the first time optimal alignments for large similar proteins (about 1,000 residues and 2,000 contacts) and used the CMO measure to cluster proteins in families. The clusters obtained were compared to SCOP classification in order to validate the measure. Extensive computational experiments showed that alignments which are off by at most 10% from the optimal value can be computed in a short time. Further experiments showed how this measure reacts to the choice of the threshold defining a contact and how to choose this threshold in a sensible way.

1 June 2003 in Journal of Computational Biology
Verified
Journal Article
Closed access
VBVineet Bafna
Vineet Bafna
DGDan Gusfield
Dan Gusfield
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
SYShibu Yooseph
Shibu Yooseph
A full haplotype map of the human genome will prove extremely valuable as it will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. A haplotype map project has been announced by NIH. The biological key to that project is the surprising fact that some human genomic DNA can be partitioned into long blocks where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected (Helmuth, 2001; Daly et al., 2001; Stephens et al., 2001; Friss et al., 2001). In this paper we explore the algorithmic implications of the no-recombination in long blocks observation, for the problem of inferring haplotypes in populations. This assumption, together with the standard population-genetic assumption of infinite sites, motivates a model of haplotype evolution where the haplotypes in a population are assumed to evolve along a coalescent, which as a rooted tree is a perfect phylogeny. We consider the following algorithmic problem, called the perfect phylogeny haplotyping problem (PPH), which was introduced by Gusfield (2002) - given n genotypes of length m each, does there exist a set of at most 2n haplotypes such that each genotype is generated by a pair of haplotypes from this set, and such that this set can be derived on a perfect phylogeny? The approach taken by Gusfield (2002) to solve this problem reduces it to established, deep results and algorithms from matroid and graph theory. Although that reduction is quite simple and the resulting algorithm nearly optimal in speed, taken as a whole that approach is quite involved, and in particular, challenging to program. Moreover, anyone wishing to fully establish, by reading existing literature, the correctness of the entire algorithm would need to read several deep and difficult papers in graph and matroid theory. However, as stated by Gusfield (2002), many simplifications are possible and the list of "future work" in Gusfield (2002) began with the task of developing a simpler, more direct, yet still efficient algorithm. This paper accomplishes that goal, for both the rooted and unrooted PPH problems. It establishes a simple, easy-to-program, O(nm2)-time algorithm that determines whether there is a PPH solution for input genotypes and produces a linear-space data structure to represent all of the solutions. The approach allows complete, self-contained proofs. In addition to algorithmic simplicity, the approach here makes the representation of all solutions more intuitive than in Gusfield (2002), and solves another goal from that paper, namely, to prove a nontrivial upper bound on the number of PPH solutions, showing that that number is vastly smaller than the number of haplotype solutions (each solution being a set of n pairs of haplotypes that can generate the genotypes) when the perfect phylogeny requirement is not imposed.

1 November 2004 in INFORMS Journal on Computing
Verified
Journal Article
Closed access
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
Cristina Maria PinottiCristina Maria Pinotti
Cristina Maria Pinotti
RRRomeo Rizzi
Romeo Rizzi
In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a 2k− 1-approximation algorithm for the case in which each genotype has at most k ambiguous positions. We further give a new integer-programming formulation that has (for the first time) a polynomial number variables and constraints. Finally, we give approximation algorithms, not based on linear programming, whose running times are almost linear in the input size.

1 January 2000 in SIAM Journal on Computing
Verified
Journal Article
Closed access
BWBang Ye Wu
Bang Ye Wu
LANCIA GIUSEPPELANCIA GIUSEPPE
LANCIA GIUSEPPE
VBVineet Bafna
Vineet Bafna
KCKun-Mao Chao
Kun-Mao Chao
RRR. Ravi
R. Ravi
CTChuan Yi Tang
Chuan Yi Tang
Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the tree. Finding a spanning tree of minimum routing cost is NP-hard, even when the costs obey the triangle inequality. We show that the general case is in fact reducible to the metric case and present a polynomial-time approximation scheme valid for both versions of the problem. In particular, we show how to build a spanning tree of an n-vertex weighted graph with routing cost at most $(1+\epsilon)$ of the minimum in time $O(n^{O({\frac{1}{\epsilon}}% )})$. Besides the obvious connection to network design, trees with small routing cost also find application in the construction of good multiple sequence alignments in computational biology. The communication cost spanning tree problem is a generalization of the minimum routing cost tree problem where the routing costs of different pairs are weighted by different requirement amounts. We observe that a randomized O(log n log log n)-approximation for this problem follows directly from a recent result of Bartal, where n is the number of nodes in a metric graph. This also yields the same approximation for the generalized sum-of-pairs alignment problem in computational biology.