关于带路和收费公路问题与重复,缺失,部分标记和不确定测量的近似和精确的优化算法.
C S Elder1, Minh Hoang2, Mohsen Ferdosi1
1Ray and Stephanie Lane Computational Biology Department, Carnegie Mellon University, Pittsburgh Pennsylvania, USA.
概括
收费公路问题从距离数据中重建点集. 新的优化算法有效地解决了杂的高速公路实例,提高了生物应用的可扩展性和准确性.
科学领域:
- 计算生物学 计算生物学
- 优化优化 优化优化
- 生物信息学是一种生物信息学.
背景情况:
- 收费公路问题涉及从对距离重建一维点集,这对分子结构,基因组学和质谱学至关重要.
- 传统的算法与杂的距离数据作斗争,导致NP-hard复杂性和指数式时间/空间要求.
研究的目的:
- 将杂的收费公路问题重新定义为一个优化任务,同时确定点位置和距离顺序.
- 开发强大的和可扩展的算法来解决收费公路问题,包括对现实世界的约束和变化的扩展,比如带路问题.
主要方法:
- 一个新的双层优化框架,旨在高效地解决高速公路问题,能够处理大数据集 (高达10万点).
- 扩展框架以适应特定领域的约束,如重复,缺失或部分标记的距离.
- 为需要全局最佳性的小规模问题制定整数线性程序 (ILP),具有通用凸起的目标和扩展的公式,以最大限度地减少二进制变量.
主要成果:
- 双级算法在合成和真实部分消化数据上展示了最先进的可扩展性,匹配或超越现有方法.
- 该ILP有效地恢复地面真相任务,并在小规模实例上实现高质量的重建.
- 算法成功地扩展到解决环路问题 (圆上的点) 和处理各种数据缺陷.
结论:
- 开发的基于优化的方法为杂的高速公路问题及其变体提供了强大而可扩展的解决方案.
- 双层框架和ILP为分子结构确定和其他生物信息学应用提供了有效的工具.
- 有开源实现可用,促进进一步的研究和应用.
相关概念视频
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
44
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
44
01:17Design Example: Alignment of a Road Line Using GIS
43
The alignment of a road line using Geographic Information Systems (GIS) is a critical process in civil engineering, combining advanced technology with practical decision-making. This methodology begins with the collection of geospatial data, including information on land cover, geomorphology, drainage patterns, slope, and contour details. Such data is typically acquired through satellite imagery and GIS tools, offering a comprehensive understanding of the terrain.Once the data is gathered, it...
43
01:10Design Example: Measuring Distance Between Two Points with Obstructions
28
When measuring distances in areas with physical obstructions, such as a lake in a field, surveyors must employ techniques to calculate accurate lengths without direct line measurements. One effective method is the offset technique, which allows for precise distance estimation over inaccessible stretches.In this scenario, a surveyor must measure a side of an area that crosses a lake. Since the measuring tape cannot span the lake, the surveyor begins by establishing a baseline that aligns with...
28
01:26Areas Within Irregular Boundaries
68
Calculating areas within irregular boundaries, such as along rivers or curved roads, is crucial in various fields, including surveying, engineering, and environmental management. Surveyors often begin by creating a traverse, a connected series of straight lines approximating the area's boundary. The coordinates of each traverse point are essential for calculating the enclosed area. The double meridian distance formula is a widely used technique for this purpose. This method utilizes the...
68
01:12Trial and Error and Algorithm
99
A problem-solving strategy is a plan of action used to find a solution. Different strategies have distinct action plans. Trial and error involves trying different solutions until one works. For instance, to fix a broken printer, you might check ink levels, ensure the paper tray isn't jammed, and verify the printer's connection to your laptop. This method can be time-consuming but is commonly used. Thomas Edison, for example, used trial and error to find a suitable filament for the light...
99
01:21Manipulation and Analysis
21
GIS manipulation and analysis functions are vital for decision-making and planning. These activities range from data retrieval tasks, such as selecting information based on specific criteria, to advanced analytical techniques that address complex spatial problems.One critical GIS analysis method is overlaying, which combines multiple data layers to examine impacts. For example, overlaying a river-dammed lake boundary with road networks can identify affected infrastructure. Another common...
21